题目描述

波尔图足球俱乐部和本菲卡足球俱乐部是葡萄牙最大的两支球队。两队交锋时，会有大量球迷从全国各地赶来观看比赛。本菲卡球迷协会也将从里斯本前往波尔图观看即将举行的比赛。

为了避免他们与波尔图球迷协会发生冲突，国家警察希望尽可能推迟本菲卡球迷协会抵达波尔图的时间。

葡萄牙的道路网络可以表示为一个有 $n$ 个顶点、$m$ 条边的简单、无向、无权、连通图：

• 顶点表示城镇；
• 边表示道路；
• 顶点 $1$ 表示里斯本，即球迷协会的起点；
• 顶点 $n$ 表示波尔图，即球迷协会的终点。

球迷协会希望通过尽可能少的道路到达波尔图。

警察始终知道球迷协会当前所在的位置。为了延迟他们抵达，警察可以在任意时刻选择恰好一条道路并将其永久封锁，但球迷协会此时不能正在这条道路上行进。

警察必须且只能执行一次封路操作。道路被封锁后，球迷协会会立刻得知这一信息，并可以任意改变之后的路线。

此外，球迷协会预先知道警察将会封锁一条道路，因此可以从一开始就据此规划自己的策略。

假设双方始终采取最优策略：

• 球迷协会希望最小化经过的道路数量；
• 警察希望最大化这一数量。

请计算球迷协会从里斯本到达波尔图至少需要经过多少条道路。

如果警察能够使球迷协会永远无法到达波尔图，输出 $-1$。

输入格式

第一行包含两个整数 $n,m$：

$$2\le n\le 200000,$$ $$n-1\le m\le \min\left(\frac{n(n-1)}2,200000\right).$$

接下来 $m$ 行，每行包含两个整数 $s_i,t_i$：

$$1\le s_i,t_i\le n,$$

表示第 $i$ 条道路连接城镇 $s_i$ 和 $t_i$。

保证：

• 图连通；
• 每条道路连接两个不同的城镇；
• 不存在重边。

输出格式

输出一个整数，表示在双方均采取最优策略时，球迷协会从里斯本到达波尔图至少需要经过的道路数量。

样例 1

输入

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

输出

5

说明

道路网络如下图所示：

样例 1 道路网络

警察的最优策略是等到球迷协会来到与终点相邻的顶点，再封锁通向终点的道路。

球迷协会可以先沿上方路径从 $1$ 到 $2$。当道路 $(2,5)$ 被封锁后，再返回 $1$，并沿 $1\to3\to4\to5$ 到达终点，总共经过 $5$ 条道路。

样例 2

输入

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

输出

9

说明

道路网络如下图所示：

样例 2 道路网络

双方的一组最优策略是先沿上方路径 $1\to2\to3\to4\to5$ 行进。警察随后封锁道路 $(5,11)$，球迷协会改走：

$$5\to4\to3\to6\to7\to11.$$

总共经过 $9$ 条道路。

样例 3

输入

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

输出

5

说明

道路网络如下图所示：

样例 3 道路网络

如果球迷协会到达顶点 $2$，警察封锁道路 $(2,3)$；如果球迷协会到达顶点 $5$，警察封锁道路 $(5,6)$。

球迷协会的一条最优路线为：

$$1\to2\to1\to5\to6\to8,$$

总共经过 $5$ 条道路。