# Reverse the graph

Very easy

Execution time limit is 6 seconds

Runtime memory usage limit is 256 megabytes

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

## Input

First line contains two integers $n$ and $m(1≤n,m≤2⋅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≤x_{i},y_{i}≤n)$, denoting that the $i$-th directed edge connects vertices from $x_{i}$ to $y_{i}$.

## Output

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

## Examples

Input #1

Answer #1

Submissions 3K

Acceptance rate 29%