# Pepcoder And Reversing

easy

You are given 2 integers N and M , N is the number of vertices, M is the number of edges. You'll also be given ai and bi where ai and bi represents an edge from a vertex ai to a vertex bi. You have to find the minimum number of edges you have to reverse in order to have atleast one path from vertex 1 to N, where the vertices are numbered from 1 to N.

## Constraints

1<= N <= 10^4 1<= M <= 10^6 1<= ai, bi <= N

## Format

### Input

First line contains two space separated integers,N and M. Then M lines follow, each line has 2 space separated integers ai and bi.

### Output

Print the minimum number of edges we need to revert. If there is no way of having at least one path from 1 to N, print -1.

## Example

Sample Input

7 7
1 2
3 2
3 4
7 4
6 2
5 6
7 5

### Sample Output

2