该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

同度跳跃

题目描述

给定一张包含 $n$ 个点、$m$ 条边的无向简单图，点的编号从 1 到 $n$。

记点 $i$ 的度数为 $\deg(i)$。

你初始位于点 1，目标是到达点 $n$。

每次操作，你可以执行以下两种操作之一：

• 普通移动：沿图中的一条边，从当前点移动到一个相邻点；
• 同度跳跃：若当前位于点 $u$，则可以选择任意一个满足 $\deg(v)=\deg(u)$ 且 $v\neq u$ 的点 $v$，直接跳跃到点 $v$。

但是，第二种操作有如下限制：

• 对于任意一个度数值 $d$，这种“同度跳跃”在整条路径中最多只能使用一次。

也就是说，若你已经在某个度数为 $d$ 的点上使用过一次同度跳跃，那么之后即使再次到达度数仍为 $d$ 的点，也不能再次触发该度数对应的跳跃。

请你求出从起点 1 到达终点 $n$ 的最少操作次数。如果无法到达，输出 -1。

输入格式

第一行输入两个整数 $n,m$，表示图中的点数和边数。

接下来 $m$ 行，每行输入两个整数 $u,v$，表示点 $u$ 与点 $v$ 之间有一条无向边。

保证给定图为简单图，即不存在重边和自环。

数据范围

• $1 \le n \le 2\times 10^5$
• $0 \le m \le 2\times 10^5$
• $1 \le u,v \le n$
• $u \neq v$

输出格式

输出一个整数，表示从点 1 到点 $n$ 的最少操作次数。

如果无法到达，输出 -1。

输入输出样例 #1

输入 #1

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

输出 #1

2

输入输出样例 #2

输入 #2

5 2
1 2
3 4

输出 #2

-1

输入输出样例 #3

输入 #3

3 0

输出 #3

1

说明/提示

样例1：

图中各点度数分别为：

• $\deg(1)=2$
• $\deg(2)=2$
• $\deg(3)=2$
• $\deg(4)=2$
• $\deg(5)=1$
• $\deg(6)=1$

一种最优方案为：

• 从起点 1 使用一次同度跳跃到达点 3（因为 $\deg(1) = \deg(3) = 2$）；
• 再沿普通边从点 3 移动到点 6。

共进行 2 次操作。

样例3：

图中有 3 个孤立点，起点的度数 $\deg(1)=0$，终点的度数 $\deg(3)=0$。 直接使用一次度数为 0 的“同度跳跃”到达终点，操作次数为 1。