该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

样例解释

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

数据范围