Blockade

Time limit1sMemory limit128 MB

Summary

Given a directed graph, find the minimum number of edges whose removal disconnects server 1 from server n.

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

Problem

The internet of Bytotia is a network of servers joined by one-way links. An attacker wants to cut off every route from server 1 to server $n$ . The attacker can plant a trap on any link, and when a trap goes off it destroys the single link it sits on. The attacker uses as few traps as possible while still guaranteeing that no message can travel from server 1 to server $n$ . Find that minimum number of traps.

Input

The first line contains two integers $n$ and $m$ ( $2 \le n \le 10000$ ): the number of servers and the number of links. Servers are numbered from $1$ to $n$ . Each of the next $m$ lines contains two integers $a$ and $b$ ( $1 \le a, b \le n$ , $a \ne b$ ), describing a one-way link from server $a$ to server $b$ . There is at most one direct link between any two servers.

Output

Print a single integer: the minimum number of links that must be destroyed so that server 1 can no longer reach server $n$ .

Examples4

Example 1
Input
```
5 5
1 2
1 3
2 4
3 4
4 5
```
Expected output
```
1
```
Example 2
Input
```
4 4
1 2
2 4
1 3
3 4
```
Expected output
```
2
```
Example 3
Input
```
2 1
1 2
```
Expected output
```
1
```
Example 4
Input
```
5 6
1 2
1 3
1 4
2 5
3 5
4 5
```
Expected output
```
3
```