给定一张n个顶点，m条边的带权图，顶点编号1~n。

现在需要从地图中寻找出从起点1，到终点n的最少换乘路线。最少换乘路线是指路途中经过的顶点数量最少。

你的程序将输入m+1行。 第一行包含两个空格隔开的整数，表示n和m。

接下来m行，每行两个整数，分别表示u、v，表示从顶点u到顶点v有一条连边。

n，m≤1,000

输出仅一行，一个整数，表达答案

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

2

求思路或代码