Your life

Interview

Time limit1sMemory limit256 MB

Summary

Find the fewest directed moves from node 1 to node N in a graph where every edge goes forward, or report -1 when the goal is unreachable.

Level: Easy3 of 10
Topics: BFS, Shortest path, Graph
Solved: No attempts yet

Problem

The situations you can run into while chasing a dream are drawn as a graph. All of them are compressed into $N$ situations numbered 1 to $N$ . You are in situation 1 right now, and situation $N$ is the single dream you want to reach.

A situation changes according to your choice. There are $M$ changes you can choose from, each given as a pair $x$ , $y$ . It means that while you are in situation $x$ you may choose to move to situation $y$ , and $x < y$ is guaranteed.

Can you reach the dream? If you can, how many changes does it take when you keep the number of changes as small as possible?

Input

The first line contains the natural numbers $N$ and $M$ separated by a space, where $1 \le N \le 100000$ and $0 \le M \le 200000$ .

Each of the next $M$ lines contains the natural numbers $x$ and $y$ separated by a space, where $1 \le x < y \le N$ . The same change may be given more than once.

Output

If you can reach the dream, print the minimum number of situation changes it takes. Otherwise print -1.

Hint

In the first example you move from situation 1 to situation 2 and then from situation 2 to situation 4, so two changes are enough.

Examples2

Example 1
Input
```
4 4
1 2
2 3
3 4
2 4
```
Expected output
```
2
```
Example 2
Input
```
1 0
```
Expected output
```
0
```