有个地方有一些城镇，城镇与城镇间有铁路或公路相连，如果有铁路相连，就不会有公路相连，没有铁路连接的城镇就会有公路相连。
给你 n 个城镇， m 条铁路线，问同时从城镇1出发，分别坐火车和坐汽车到达城镇n，求两者都到达的时候最少的用时。
其中火车和汽车不能同时到达中间点。
第一行两个整数 n 和 m
表示城镇的数量和铁路的数量。
接下来 m 行每行两个整数 u 和 v ，表示城镇 u 到 v 有铁路相连。
一个整数，表示两种交通工具都到达终点的最少用时，如果 其中有一种交通工具不能到达或都不能到达终点 ，输出 -1 。
相邻两地乘火车或汽车的用时都是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
n\leq 400
(0<=m<=n×(n-1)/2