You are given a directed graph with $n$ vertices and $m$ edges. The vertices in the graph are numbered from $1$ to $n$. What is the minimum number of edges you need to reverse in order to have at least one path from vertex $1$ to vertex $n$. \InputFile First line contains two integers $n$ and $m\:(1 \le n, m \le 2 \cdot 10^6)$ --- the number of vertices and the number of edges. The $i$-th line of the next $m$ lines contains two integers $x_i$ and $y_i\:(1 \le x_i, y_i \le n)$, denoting that the $i$-th directed edge connects vertices from $x_i$ to $y_i$. \OutputFile Print the minimum number of edges we need to invert. If there is no way of having at least one path from $1$ to $n$, print $-1$. \includegraphics{https://static.e-olymp.com/content/a3/a323657425ee743acea3408abb66e49eb10c4678.gif}