The Two Routes

有个地方有一些城镇，城镇与城镇间有铁路或公路相连，如果有铁路相连，就不会有公路相连，没有铁路连接的城镇就会有公路相连。给你 $n$ 个城镇， $m$ 条铁路线，问同时从城镇1出发，分别坐火车和坐汽车到达城镇n，求两者都到达的时候最少的用时。其中火车和汽车不能同时到达中间点。 ### 输入格式 第一行两个整数 $n$ 和 $m$ $(0<=m<=n×(n-1)/2$ 表示城镇的数量和铁路的数量。 接下来 $m$ 行每行两个整数 $u$ 和 $v$ ，表示城镇 $u$ 到 $v$ 有铁路相连。 ### 输出格式 一个整数，表示两种交通工具都到达终点的最少用时，如果**其中有一种交通工具不能到达或都不能到达终点**，输出 $-1$ 。 相邻两地乘火车或汽车的用时都是1 感谢@_UKE自动机_ 提供的翻译

In Absurdistan, there are $ n $ towns (numbered $ 1 $ through $ n $ ) and $ m $ bidirectional railways. There is also an absurdly simple road network — for each pair of different towns $ x $ and $ y $ , there is a bidirectional road between towns $ x $ and $ y $ if and only if there is no railway between them. Travelling to a different town using one railway or one road always takes exactly one hour. A train and a bus leave town $ 1 $ at the same time. They both have the same destination, town $ n $ , and don't make any stops on the way (but they can wait in town $ n $ ). The train can move only along railways and the bus can move only along roads. You've been asked to plan out routes for the vehicles; each route can use any road/railway multiple times. One of the most important aspects to consider is safety — in order to avoid accidents at railway crossings, the train and the bus must not arrive at the same town (except town $ n $ ) simultaneously. Under these constraints, what is the minimum number of hours needed for both vehicles to reach town $ n $ (the maximum of arrival times of the bus and the train)? Note, that bus and train are not required to arrive to the town $ n $ at the same moment of time, but are allowed to do so.

The first line of the input contains two integers $ n $ and $ m $ ( $ 2<=n<=400 $ , $ 0<=m<=n(n-1)/2 $ ) — the number of towns and the number of railways respectively. Each of the next $ m $ lines contains two integers $ u $ and $ v $ , denoting a railway between towns $ u $ and $ v $ ( $ 1<=u,v<=n $ , $ u≠v $ ). You may assume that there is at most one railway connecting any two towns.

Output one integer — the smallest possible time of the later vehicle's arrival in town $ n $ . If it's impossible for at least one of the vehicles to reach town $ n $ , output $ -1 $ .

4 2
1 3
3 4

2

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

-1

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

3

In the first sample, the train can take the route  and the bus can take the route . Note that they can arrive at town $ 4 $ at the same time. In the second sample, Absurdistan is ruled by railwaymen. There are no roads, so there's no way for the bus to reach town $ 4 $ .