A metro system has
A commuter starts at station
The first line contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression — the number of stations and the number of tracks.
Each of the next KaTeX can only parse string typed expression lines contains two integers KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, meaning there is a two-way track between stations KaTeX can only parse string typed expression and KaTeX can only parse string typed expression.
Print the minimum number of stops to travel from station KaTeX can only parse string typed expression to station KaTeX can only parse string typed expression. If it is not reachable, print KaTeX can only parse string typed expression.
Input
6 6
1 2
2 3
3 6
1 4
4 5
5 63One shortest route is KaTeX can only parse string typed expression, using KaTeX can only parse string typed expression stops. The other route KaTeX can only parse string typed expression also needs KaTeX can only parse string typed expression stops.
Example 2:
Input
4 2
1 2
3 4-1Stations KaTeX can only parse string typed expression and KaTeX can only parse string typed expression are disconnected from stations KaTeX can only parse string typed expression and KaTeX can only parse string typed expression, so station KaTeX can only parse string typed expression can never be reached from station KaTeX can only parse string typed expression.
Example 3:
Input
3 2
1 3
1 21There is a direct track from station KaTeX can only parse string typed expression to station KaTeX can only parse string typed expression, so a single stop suffices.