波尔图足球俱乐部（FC Porto）和本菲卡足球俱乐部（SL Benfica）是葡萄牙最大的两支足球队。自然地，当这两支球队交手时，全国各地会有许多人前往观看比赛。这其中包括本菲卡球迷俱乐部，他们将从里斯本前往波尔图观看即将到来的比赛。为了避免他们与波尔图球迷俱乐部之间产生紧张关系，国家警察希望尽可能推迟他们到达波尔图的时间。

葡萄牙的公路网可以建模为一个简单的、无向的、无权重的连通图，包含 $n$ 个顶点和 $m$ 条边，其中顶点代表城镇，边代表道路。顶点 1 对应里斯本（即球迷俱乐部的出发点），顶点 $n$ 对应波尔图（即球迷俱乐部的目的地）。球迷俱乐部希望最小化他们到达波尔图所经过的道路数量。

警察一直在密切关注球迷俱乐部，因此他们总是知道球迷俱乐部所在的位置。为了推迟他们的到达，警察可以在任何时候选择恰好一条道路并将其封锁，前提是球迷俱乐部当前没有正在通过该道路。警察只能执行此操作一次，一旦封锁，该道路将永久关闭。一旦警察封锁了一条道路，球迷俱乐部会立即得知该道路已被封锁，并可以根据需要更改路线。此外，球迷俱乐部知道警察计划封锁某条道路，并可以据此规划路线。

假设球迷俱乐部和警察都始终做出最优选择，请确定球迷俱乐部从里斯本前往波尔图所需经过的最少道路数量。如果警察能够阻止球迷俱乐部到达波尔图，则输出 $-1$。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($2 \le n \le 200\,000$, $n-1 \le m \le \min\{n(n-1)/2, 200\,000\}$)，分别表示城镇数量和公路网中的道路数量。

接下来的 $m$ 行，每行包含两个整数 $s_i$ 和 $t_i$ ($1 \le s_i, t_i \le n$)，表示第 $i$ 条道路连接的两个城镇。

保证公路网是连通的，每条道路连接两个不同的城镇，且没有重复的道路。

输出格式

输出球迷俱乐部从里斯本前往波尔图所需经过的最少道路数量。

样例

输入 1

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

输出 1

5

说明 1

公路网如下图所示：

注意，警察的最优策略是等待球迷俱乐部到达目的地（即顶点 5）的相邻顶点，然后封锁连接该顶点与目的地的边。球迷俱乐部的最优策略是沿上方的路径走（从 1 到 2），在看到 2 到 5 之间的边被封锁后，他们会折返经过 2 回到 1，然后沿下方的路径（1 到 3 到 4 到 5）走。在这种情况下，经过的道路总数为 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

输出 2

9

说明 2

公路网如下图所示：

这里有多种策略，但可以验证，对于警察和球迷俱乐部双方而言，最优策略是沿上方的路径（$1 \to 2 \to 3 \to 4 \to 5$）走，然后警察封锁 5 到 11 的边，因此球迷俱乐部绕道走 $5 \to 4 \to 3 \to 6 \to 7 \to 11$。该策略下经过的道路总数为 9。

输入 3

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

输出 3

5

说明 3

公路网如下图所示：

警察的最优策略是：如果球迷俱乐部到达顶点 2，则封锁 2 到 3 的边；或者如果球迷俱乐部到达顶点 5，则封锁 5 到 6 的边。在这种情况下，最优路径是 $1 \to 2 \to 1 \to 5 \to 6 \to 8$。该策略下经过的道路总数为 5。