교통 돕기

면접 대비

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

요약

지점 N개와 일방통행 도로 M개가 주어질 때, 모든 지점이 서로 오갈 수 있도록 추가해야 하는 일방통행 다리의 최소 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 그래프, DFS, 위상 정렬
정답자: 아직 제출이 없습니다

문제

네이션로니아 대통령이 나라의 모든 도로를 일방통행으로 바꾸라는 법령을 내렸다. 변경을 제대로 계획하지 않은 탓에 사람들은 출근하지 못하거나 퇴근 후 집에 돌아가지 못했다. 그 결과 여러 도시에서 혼란과 폭동이 일어났다.

대통령은 탄핵되었고, 새 정부는 이 문제를 풀기 위해 과학자 팀을 꾸렸다. 팀은 다시 알고리즘 복잡도 전문가인 당신을 고용해 해법을 효율적으로 계산하도록 도와 달라고 요청했다.

각 도시에는 기준점들이 있고, 기준점 두 개를 잇는 일방통행 도로가 있다. 도시를 완전히 연결하려면 최소 몇 개의 일방통행 다리를 건설해야 하는지 구하라. 다리 역시 기준점 두 개를 잇는다.

입력

첫 줄에 두 정수 $N$ 과 $M$ 이 주어진다 ( $1 ≤ N ≤ 10^4$ , $1 ≤ M ≤ 10^6$ ). $N$ 은 기준점의 개수이고 $M$ 은 도로의 개수이다. 이어지는 $M$ 개의 줄에는 두 정수 $R$ 과 $S$ ( $1 ≤ R, S ≤ N$ , $R \ne S$ )가 주어지며, 이는 $R$ 에서 $S$ 로 이어지는 도로를 뜻한다. 이 도로의 모든 차량은 $R$ 에서 멀어져 $S$ 방향으로 이동해야 한다.

출력

주민들을 만족시키는 데 필요한 다리의 최소 개수를 한 줄에 출력한다.

예제5

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