Reverse the graph

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