Alice 和 Bob 在一个包含 $N$ 个节点和 $M$ 条边的简单连通图上玩游戏。

Alice 将图中的每条边涂成红色或蓝色。

路径是一系列边的序列，其中每相邻的两条边都有一个公共节点。如果这对边中的第一条边与第二条边的颜色不同，则称为一次“颜色改变”。

在 Alice 对图进行染色后，Bob 选择一条从节点 $1$ 开始并以节点 $N$ 结束的路径。他可以选择图上的任意路径，但他希望最小化路径中的颜色改变次数。Alice 希望通过选择一种边染色方案，使得 Bob 无论选择哪条路径，都必须进行尽可能多的颜色改变。无论 Bob 选择哪条路径，Alice 最多能强制 Bob 进行多少次颜色改变？

输入格式

第一行包含两个整数 $N$ 和 $M$，其中 $2 \le N \le 100\,000$ 且 $1 \le M \le 100\,000$。接下来的 $M$ 行包含两个整数 $a_i$ 和 $b_i$，表示节点 $a_i$ 和 $b_i$ 之间的一条无向边（$1 \le a_i, b_i \le N, a_i \neq b_i$）。

图中所有边都是唯一的。

输出格式

输出 Alice 可以强制 Bob 在从节点 $1$ 到节点 $N$ 的路径上进行的颜色改变的最大次数。

样例

输入 1

3 3
1 3
1 2
2 3

输出 1

0

输入 2

7 8
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7

输出 2

3

Figure 1. A graph with colored edges.