Reverse the graph

A directed graph with $n$ vertices and $m$ edges is given, with vertices numbered from $1$ to $n$. Find the minimum number of edges that need to be reversed so that there exists at least one path from vertex $1$ to vertex $n$.

Input

The first line contains two integers $n$ and $m(1\le n,m\le 2\cdot 10^6)$ — the number of vertices and edges in the graph. Each of the following $m$ lines contains two integers $x_i$ and $y_i(1\le x_i,y_i\le n)$, indicating that the $i$-th directed edge goes from vertex $x_i$ to vertex $y_i$.

Output

Print the minimum number of edges that need to be reversed. If it is not possible to obtain a path from vertex $1$ to vertex $n$, print $-1$.

Examples