题目描述

有 $n$ 个 城市，从 $1$ 到 $n$ 给他们编号，它们之间由一些单向道路（即一条道路只能从一个方向走向另一个方向，反之不行）相连，现在要求从 $1$ 走到 $n$ 。问最少经过几条路。

保证存在从 $1$到 $n$ 的路径。

输入格式

第一行两个整数 $n$ 和 $m$，表示有多少个城市和多少条道路。

接下来 $m$ 行，每行两个整数 $s$ 、$t$ ，即有一条从 $s$ 到 $t$ 的路。

输出格式

一行一个整数，即从 $1$ 到 $n$ 最少经过几条路。

样例

输入样例

6 6 
1 3 
2 6 
3 6 
3 2 
6 4 
4 5

样例输出

2

样例解释

数据范围与提示

$70\%$ 的数据，$1 \le n, m \le 10^3$

$100\%$ 的数据，$1 \le n,m \le 10^5$