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