/ TYWZ / 题库 /

Basic Graph - C

Basic Graph - C

Description

输入给出一张不带权的无向图,你需要输出从1号结点到达n号结点的最短路径的长度。

Format

Input

第一行有两个整数n, m; n表示顶点的个数,m表示边的条数。
接下来m行,每行有两个整数a, b; 表示顶点a与顶点b相连。
注意可能存在自环与重边。

Output

一个整数,表示1到n的最短路径的长度。若从1无法到达n,则输出-1。

Sample 1

Input

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

Output

1

Limitation

1s, 128000KiB for each test case.

Hint

对于30%的数据,1 <= n <= 10,1<=m<=100;
对于70%的数据,1 <= n <= 200, 1<=m<=2000;
对于100%的数据,1 <= n <= 2000, 1<=m<=2000。

Source

TYWZ

信息

难度
8
分类
(无)
标签
(无)
递交数
110
已通过
16
通过率
15%
上传者

相关

在下列比赛中:

图及图的遍历