Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

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$.

On each turn, player B selects $k$ nodes, and locks them; however, she cannot choose node $N$ nor the node where the coin is currently located at. Then, player A may move the coin to any adjacent (unlocked) node of the coin. Locked nodes are kept locked until the end of the turn and then are unlocked.We want to find the smallest $k$ such that player B can prevent A from moving the coin to node $N$.

Input

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.

Output

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$.

Sample test(s)