本题由李博放同学原创！在此感谢！
真三国无双系列

②赵云杀郭嘉
某日赵云要杀郭嘉
于是开了个无双 飚了个玄武 簸出了基地
他已经知道郭嘉的位置（血池）
由于玄武及无双的时间有限 他必须选择一条最短的路
以便在最短的时间内杀了郭嘉（其实是被郭嘉杀）

输入
第一行两个整数n，m，（n<=m/2,m<=1000000）。
接下来m行每行两个整数a，b，表示a，b间的距离为1。
赵云的基地在1处 郭嘉在n处

输出
一个整数s，表示从1到n最短路的长度，无法到达则输出999999999。

样例

input
5 4

1 2
2 4
3 4
4 5
output
3