题目描述

阿瓦想要去 A 市旅游！

A 市作为一个旅游城市，一共有 $n$ 个景点，编号为 $1,2,\cdots,n$。

为了连接这些景点，A 市建立了 $m$ 条双向公交专用道，编号为 $1,2,\cdots,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

4 2
1 3
3 4

输出 #1

2

输入输出样例 #2

输入 #2

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

输出 #2

-1

说明/提示

样例 1 解释

公共汽车：$1\rightarrow 3 \rightarrow4$，出租车：$1\rightarrow2\rightarrow4$。

样例 2 解释

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

数据范围

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

测试点编号	$n$
$2 \sim 4$	$2 \leq n \leq 7$
$5 \sim 10$	$2 \leq n \leq 70$
$11 \sim 16$	$2 \leq n\leq 400$
$17 \sim 20$	$2 \leq n\leq 5000$