某国家有 $n$ 个城市（编号 $1 \sim n$）和 $m$ 条双向铁路。

每条铁路连接两个不同的城市，没有两条铁路连接同一对城市。

除了铁路以外，该国家还有公路。

对于每对不同的城市 $x,y$，当且仅当它们之间没有铁路时，它们之间会存在一条双向公路。

经过每条铁路或公路都需要花费 $1$ 小时的时间。

现在有一列火车和一辆汽车同时离开城市 $1$，它们的目的地都是城市 $n$。

它们不会在途中停靠（但是可以在城市 $n$ 停靠）。

火车只能沿铁路行驶，汽车只能沿公路行驶。

请你为它们规划行进路线，每条路线中可重复经过同一条铁路或公路，但是为了避免发生事故，火车和汽车不得同时到达同一个城市（城市 $n$ 除外）。

请问，在这些条件的约束下，两辆车全部到达城市 $n$ 所需的最少小时数，即求更慢到达城市 $n$ 的那辆车所需的时间的最小值。

注意，两辆车允许但不必要同时到达城市 $n$。

输入格式

第一行包含整数 $n$ 和 $m$。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示城市 $u$ 和城市 $v$ 之间存在一条铁路。

输出格式

一个整数，表示所需的最少小时数。

如果至少有一辆车无法到达城市 $n$，则输出 $-1$。

数据范围

前 $6$ 个测试点满足 $2 \le n \le 10$，$0 \le m \le 10$。
所有测试点满足 $2 \le n \le 400$，$0 \le m \le \frac{n(n-1)}{2}$，$1 \le u,v \le n$。

输入样例1：

4 2
1 3
3 4

输出样例1：

2

输入样例2：

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

输出样例2：

-1

输入样例3：

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

输出样例3：

3