JZ市作为一个旅游城市，一共有n个景点，从1到n编号。

为了连接这些景点，JZ市建立了m条双向公交专用道，从1到m编号。

除了公交专用道，各个景点还有很多出租专用道。对于任意一对的景点x和y（x \ne y），x和y之间存在一条双向出租专用道，当且仅当它们之间没有公交专用道。

从任意景点出发，经过一条公交/出租专用道前往其他的景点总是需要1小时。

一辆出租车和一辆公共汽车同时离开景点1。公共汽车只能沿公交专用道行驶，出租车只能沿出租专用道行驶。它们都有相同的目的地，即景点n，并且在途中不做任何停留，但可以在景点n等待。

你正在为出租车和公共汽车规划路线。出租车/公共汽车可以多次经过任何出租专用道/公交专用道。你需要考虑的最重要方面之一是安全：为了避免在道路口发生事故，出租车和公共汽车不得同时到达同一个景点（景点n除外）。

在这些限制条件下，你需要求出两辆车到达景点n所需的最少小时数，即使得公共汽车和出租车到达时间的较大值最小。请注意，公共汽车和出租车车不必同时到达景点n。

输入的第一行包含两个整数n和m，分别是景点的数量和公交专用道的数量。

接下来的m行中的每一行包含两个整数u和v，表示景点u和v之间存在一条双向公交专用道（1\leq u \neq v \leq n）。

任何两个景点之间最多有一条公交专用道。

输出一个整数，表示答案。 

如果至少有一辆车辆不可能到达景点n，则输出-1。

对于样例1，公共汽车：1->3->4，出租车：1->2->4。

对于样例2，只有公交专用道，没有出租专用道，所以出租车不可能到达景点n，答案是-1。

### 数据范围

|                         测试点编号                          |         n         |

| :---------------------------------------------------------: | :-----------------: |

|                         1 \sim 4                          |  1 \leq n \leq 7  |

|                         5 \sim 10                         | 1 \leq n \leq 70  |

|                        11 \sim 16                         | 1 \leq n\leq 400  |

|                        17 \sim 20                         | 1 \leq n\leq 5000 |

| 对于所有数据，0\leq m\leq \min\{10^5,\frac{n(n-1)}{2}\}。 |                     |