[R77E]联络 - 代码源竞赛平台

时空限制

1S/512M

题目描述

一张联络网中有 $n$ 个站点，编号为 $1$ 到 $n$。其中已经铺设了 $m$ 条双向线路，每条线路连接两个不同的站点，任意两个站点之间至多有一条线路。

现在要把一条消息从站点 $1$ 传到站点 $n$。每次传递都必须从当前站点到另一个站点，并按下面的规则交替进行：

• 第奇数次传递，也就是说第 $1,3,5,\ldots$ 次传递，两个站点之间必须有已铺设的线路。
• 第偶数次传递，也就是说第 $2,4,6,\ldots$ 次传递，两个站点之间必须没有已铺设的线路。

传递过程中可以重复经过同一个站点。求消息到达站点 $n$ 至少需要传递多少次。如果无法到达，输出 $-1$。特别地，当 $n=1$ 时，消息已经位于目标站点，答案为 $0$。

格式

输入格式

第一行包含一个整数 $n$ 和一个整数 $m$，分别为站点数量和已铺设的双向线路数量。

接下来 $m$ 行，每行包含两个正整数 $u_i,v_i$，表示第 $i$ 条线路连接站点 $u_i$ 和站点 $v_i$。

输出格式

输出一个整数，表示消息从站点 $1$ 到达站点 $n$ 所需的最少传递次数；如果无法到达，输出 $-1$。

样例

样例输入 #1

5 3
1 2
2 5
3 5

样例输出 #1

3

样例解释 #1

可以依次经过站点 $1,2,3,5$。第一次和第三次传递使用已铺设的线路，第二次传递的两个站点之间没有已铺设的线路。无法用少于三次传递到达站点 $5$。

样例输入 #2

3 2
1 2
2 3

样例输出 #2

-1

样例解释 #2

第一次只能从站点 $1$ 到达站点 $2$。站点 $2$ 与其他两个站点之间均有已铺设的线路，第二次无法继续传递。

样例输入 #3

1 0

样例输出 #3

0

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	特殊性质
$1$	$10$	$60$	无
$2$	$25$	$2000$
$3$	$15$	$10^6$	A
$4$	$50$		无特殊限制

特殊性质 A：每个站点至多与一条已铺设的线路相连。

对于 $100\%$ 的数据，满足 $1\le n\le 10^6$，$0\le m\le\min\left(\frac{n(n-1)}2,10^6\right)$，$1\le u_i,v_i\le n$，$u_i\ne v_i$；任意两个站点之间至多有一条线路。