Two players, A and B, compete on an undirected graph with $N$ nodes numbered $1$ to $N$. Player A must move a coin from node $1$ to node $N$.

The first line contains two integers $N$ and $M$ $(2 \leq N \leq 10^5, 0 \leq M \leq 10^5)$, the number of nodes and the number of edges respectively. Then $M$ lines, each with two integers $u$ and $v$ $(1 \leq u, v \leq N)$ the description of each edge.

Print the value of the smallest $k$ such that player B can prevent A from moving the coin to node $N$. If there is no such $k$, print $-1$.

Input

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

Output

1

Input

6 8
1 2
1 3
2 4
3 5
4 6
5 6
3 4
2 5

Output

2

Input

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

Output

-1