CF601A The Two Routes

有个地方有一些城镇，城镇与城镇间有铁路或公路相连，如果有铁路相连，就不会有公路相连，没有铁路连接的城镇就会有公路相连。 给你 $n$ 个城镇，$m$ 条铁路线，问同时从城镇 $1$ 出发，分别坐火车和坐汽车到达城镇 $n$，求两者都到达的时候最少的用时。其中火车和汽车不能同时到达中间点。

第一行两个整数 $n$ 和 $m~(2 \le n \le 400,0 \le m \le \frac{n\times (n-1)}2)$， 表示城镇的数量和铁路的数量。 接下来 $m$ 行每行两个整数 $u$ 和 $v~(1 \le u, v \le n, u \neq v)$，表示城镇 $u$ 到 $v$ 有铁路相连。 保证任意两个城镇之间至多有一条铁路。

一个整数，表示两种交通工具都到达终点的最少用时，如果**其中有一种交通工具不能到达或都不能到达终点**，输出 $-1$ 。 相邻两地乘火车或汽车的用时都是 $1$。 感谢@_UKE自动机_ 提供的翻译

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 $ .