题目描述

Alice和Bob在一个有N个节点和M条边的简单连通图上玩游戏。
Alice可以把图中的每条边涂成红色或蓝色。
在Alice为图着色后，Bob要选择一条从节点1开始到节点N结束的路径。
他可以选择图上的任何路径，但他想是路径中的颜色变化（从一种颜色的边走到另一种颜色的边）次数最少。Alice想选择一种涂色方式最大化，Bob必须改变颜色的次数。试求在不同着色方式下，最少的颜色变化次数的最大值？

输入格式

第一行包含两个整数值N和M，其中2≤N≤100000，1≤M≤100000
接下来的M行每行包含两个整数ai和bi，表示ai和bi之间有一条无向边（1≤ai，bi≤N，ai≠bi）

输出格式

在不同着色方式下，最少的颜色变化次数的最大值。

样例数据

input1

3 3
1 3 
1 2 
2 3

output1

0

input2

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

output2

3