도로

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

요약

방향 그래프가 주어졌을 때, 전체 그래프를 강하게 연결되도록 만들기 위해 추가해야 하는 간선의 최소 개수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, DFS, 그리디
정답자: 아직 제출이 없습니다

문제

바이트오티아에는 $n$ 개의 도시가 있습니다. 도시들은 일방통행 도로로 연결되어 있으며, 각 도로는 정확히 두 도시만 잇고 다른 도시를 거치지 않습니다. 그런데 모든 도시에서 다른 모든 도시로 이동할 수 있는 것은 아닙니다. 바이트아자르 왕은 이 문제를 해결하기로 했습니다. 새 도로를 건설하는 데는 비용이 매우 많이 들고 예산도 넉넉하지 않으므로, 왕은 당신에게 도움을 요청했습니다. 모든 도시에서 다른 모든 도시로 이동할 수 있게 만들기 위해 새로 건설해야 하는 일방통행 도로의 최소 개수를 구하세요.

다음을 수행하는 프로그램을 작성하세요.

기존 도로망의 정보를 입력받습니다.
모든 도시에서 다른 모든 도시로 이동할 수 있도록 추가로 건설해야 하는 도로의 최소 개수를 계산합니다.
그 결과를 출력합니다.

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 공백 하나로 구분되어 주어집니다 ( $2 \le n \le 10\,000$ , $0 \le m \le 100\,000$ ). 각각 도시의 수와 도로의 수를 뜻합니다. 도시에는 $1$ 번부터 $n$ 번까지 번호가 매겨져 있습니다. 이어지는 $m$ 개의 줄에는 각각 공백 하나로 구분된 두 정수가 주어집니다. 그중 $i$ 번째 줄의 두 정수 $a_i$ 와 $b_i$ ( $1 \le a_i, b_i \le n$ )는 도시 $a_i$ 에서 도시 $b_i$ 로 향하는 일방통행 도로를 나타냅니다.

출력

모든 도시에서 다른 모든 도시로 이동할 수 있도록 새로 건설해야 하는 일방통행 도로의 최소 개수를, 음이 아닌 정수 하나로 첫째 줄에 출력합니다.

힌트

예제7

예제 1

입력

예상 출력

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