题目描述

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

输入格式

第一行两个整数 $n$ 和 $m\ (0\le m\le n×(n-1)/2)$，表示城镇的数量和铁路的数量。

接下来 $m$ 行每行两个整数 $u$ 和 $v$，表示城镇 $u$ 到 $v$ 有铁路相连。

输出格式

一个整数，表示两种交通工具都到达终点的最少用时，如果其中有一种交通工具不能到达或都不能到达终点，输出 $-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