题目描述

在荒谬国（Absurdistan）里有 $n$ 个城镇（编号为 $1$ 到 $n$）和 $m$ 条双向铁路。此外，这里的公路网也极其简单——对于任意两个不同城镇 $x$ 和 $y$，如果它们之间没有铁路，则恰好有一条双向公路相连；如果它们之间有铁路，则没有公路。无论乘坐铁路还是公路，前往另一个城镇都恰好需要一小时。

一列火车和一辆巴士同时从 $1$ 号城镇出发。它们的目的地都是 $n$ 号城镇，途中不做任何停留（但可以在 $n$ 号城镇等候）。火车只能沿铁路行驶，巴士只能沿公路行驶。

你需要为这两种交通工具规划路线；每条路线可以重复使用同一条铁路或公路多次。需要考虑的一个最重要的安全因素是——为了避免在铁路道口发生事故，火车和巴士不得同时到达同一个城镇（$n$ 号城镇除外）。

在这些约束下，两辆车都到达 $n$ 号城镇所需的最少小时数是多少（即巴士和火车到达时间的较大值）？注意，巴士和火车不必同时到达 $n$ 号城镇，但也可以同时到达。

输入

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 400$，$0 \le m \le \frac{n(n-1)}{2}$）—— 分别表示城镇数量和铁路数量。

接下来 $m$ 行，每行两个整数 $u$ 和 $v$，表示城镇 $u$ 与 $v$ 之间有一条铁路（$1 \le u, v \le n$，$u \ne v$）。

你可以假设任意两个城镇之间至多有一条铁路。

输出

输出一个整数 —— 较晚到达 $n$ 号城镇的那辆车的最短可能到达时间。如果至少有一辆车无法到达 $n$ 号城镇，则输出 $-1$。

说明

在第一个样例中，火车可以走路线 $1 \to 3 \to 4$，巴士可以走路线 $1 \to 2 \to 4$。注意它们可以同时到达 $4$ 号城镇。

在第二个样例中，荒谬国完全由铁路控制。没有任何公路，因此巴士无法到达 $4$ 号城镇。

样例

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