Competitions

# 0 - 1 BFS

# Reverse the graph

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`

) - the number of vertices and the number of edges. The ^{6}**i**-th line of the next **m** lines contains two integers `x`

and _{i}`y`

(_{i}**1** ≤ `x`

, _{i}`y`

≤ _{i}**n**), denoting that the **i**-th directed edge connects vertices from `x`

to _{i}`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**.

Input example #1

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

Output example #1

2