Problem Statement

You are given a graph with $N$ vertices and $0$ edges.

You are given $M$ candidate edges. The $i$-th edge can connect vertex $a_i$ and vertex $b_i$.

Find the minimum number of edges that must be used to make vertex $1$ and vertex $N$ connected.

Also, if there is no way to make vertex $1$ and vertex $N$ connected, report that.

Input

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

• All inputs are integers.
• $2 \le N,M \le 2 \times 10^5$
• $1 \le a_i , b_i \le N$
• $a_i \neq b_i$
• If $i \neq j$, then $(a_i,b_i) \neq (a_j,b_j)$
• If $i \neq j$, then $(a_i,b_i) \neq (b_j,a_j)$

Output

If vertex $1$ and vertex $N$ can be made connected, output the minimum number of edges required to connect them.

If there is no way to make vertex $1$ and vertex $N$ connected, output $-1$.

Sample

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