一张简单连通图有 $N$ 个顶点和 $M$ 条边。小婷老师先把每条边染成红色或蓝色。之后小泽选择一条从顶点 $1$ 到顶点 $N$ 的路径，并让路径中相邻两条边颜色不同的次数尽量少；小婷老师则希望通过染色让这个最少次数尽量大。

请输出小婷老师能够保证的最大颜色变化次数。路径允许经过任意边，但小泽会选择对自己最有利的路线。

输入格式

第一行输入 $N,M$。

接下来 $M$ 行输入无向边。

输出格式

输出能够保证的最大颜色变化次数。

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

5

12 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
8 11
1 4

6

17 19
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
11 14
6 9
4 7

11

数据范围与约定

• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• 图连通且无重边