봉쇄

시간 제한1초메모리 제한128 MB

요약

방향 그래프에서 서버 1에서 서버 n으로 가는 경로를 끊기 위해 제거해야 하는 최소 간선 수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 최단 경로, BFS
정답자: 아직 제출이 없습니다

문제

바이토시아의 인터넷은 여러 서버와, 서버끼리 잇는 단방향 링크로 이루어진 네트워크입니다. 한 공격자가 서버 1에서 서버 $n$ 으로 가는 모든 통신을 끊으려고 합니다. 공격자는 어떤 링크에든 덫을 설치할 수 있고, 덫이 작동하면 그 덫이 놓인 링크 하나가 끊어집니다. 공격자는 서버 1에서 서버 $n$ 으로 어떤 메시지도 도달할 수 없게 만들면서, 사용하는 덫의 개수를 최소로 하려고 합니다. 이때 필요한 덫의 최소 개수를 구하세요.

입력

첫째 줄에 서버의 수 $n$ 과 링크의 수 $m$ 이 주어집니다 ( $2 \le n \le 10000$ ). 서버는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있습니다. 다음 $m$ 개의 줄에는 각각 두 정수 $a$ 와 $b$ 가 주어지며 ( $1 \le a, b \le n$ , $a \ne b$ ), 이는 서버 $a$ 에서 서버 $b$ 로 가는 단방향 링크가 있음을 뜻합니다. 임의의 두 서버 사이에는 직접 잇는 링크가 많아야 하나 존재합니다.

출력

서버 1이 더 이상 서버 $n$ 에 도달할 수 없게 만들기 위해 끊어야 하는 링크의 최소 개수를 한 줄에 출력하세요.

예제4

예제 1
입력
```
5 5
1 2
1 3
2 4
3 4
4 5
```
예상 출력
```
1
```
예제 2
입력
```
4 4
1 2
2 4
1 3
3 4
```
예상 출력
```
2
```
예제 3
입력
```
2 1
1 2
```
예상 출력
```
1
```
예제 4
입력
```
5 6
1 2
1 3
1 4
2 5
3 5
4 5
```
예상 출력
```
3
```