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