問題文

$N$ 頂点 $0$ 辺のグラフが与えられます。

$M$ 本の辺の候補が与えられます。$i$ 本目の辺は、頂点 $a_i$ と頂点 $b_i$ をつなぐことができます。

頂点 $1$ と頂点 $N$ を連結にするためには、最低で何本の辺を使う必要があるか求めてください。

また、どのようにしても頂点 $1$ と頂点 $N$ を連結にすることができないならばそのことを報告してください。

入力

$N\ M$
$a_1\ b_1$
$a_2\ b_2$
$\vdots$
$a_M\ b_M$

• 入力は全て整数である。
• $2 \le N,M \le 2 \times 10^5$
• $1 \le a_i , b_i \le N$
• $a_i \neq b_i$
• $i \neq j$ ならば $(a_i,b_i) \neq (a_j,b_j)$
• $i \neq j$ ならば $(a_i,b_i) \neq (b_j,a_j)$

出力

もし頂点 $1$ と頂点 $N$ を連結にできるのならば連結するために必要な辺の本数の最小値を出力してください。

どのようにしても頂点 $1$ と頂点 $N$ を連結にすることができないならば $-1$ を出力してください。

サンプル

4 3
1 3
4 2
1 2

2

5 3
1 3
5 4
4 2

-1

9 9
7 5
2 4
1 3
4 6
9 2
5 8
6 3
3 7
1 7

5