네트워크

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

요약

우선순위가 매겨진 N개의 시스템과 M개의 간선이 주어질 때, A→B와 B→C를 A→C로 합치는 연산을 반복한 뒤 남는 간선의 수를 구한다.

난이도: 보통10점 중 6점
유형: 그래프, 그리디, 수학, 조합론
정답자: 아직 제출이 없습니다

문제

회사에 $N$ 개의 네트워크 시스템 $S_1, S_2, \dots, S_N$ 과 이들을 연결하는 $M$ 개의 네트워크 $W_1, W_2, \dots, W_M$ 이 있다. 시스템에는 우선순위가 있어서 모든 네트워크는 우선순위가 높은 시스템에서 낮은 시스템으로만 전달된다. 즉 $S_A$ 에서 $S_B$ 로 전달되는 네트워크가 있다면 $A < B$ 이다.

최근 네트워크가 너무 난잡해져서 정리하기로 했다. 세 시스템 $S_A$ , $S_B$ , $S_C$ 에 대해 $S_A$ 에서 $S_B$ 로 전달되는 네트워크와 $S_B$ 에서 $S_C$ 로 전달되는 네트워크가 있으면, 이 두 네트워크를 합쳐 $S_A$ 에서 $S_C$ 로 전달되는 네트워크 하나로 간략화한다. 이때 원래의 두 네트워크는 사라지고 새 네트워크 하나가 생긴다. 같은 두 시스템을 연결하는 네트워크가 여러 개 있어도 각각 별개의 네트워크로 센다.

이 간략화를 반복해서 네트워크의 수를 최대한 줄이려고 한다. 남은 네트워크의 수를 구하여라.

입력

첫째 줄에 $N$ 과 $M$ 이 주어진다. ( $1 \le N, M \le 10^6$ )

다음 $M$ 개의 줄 중 $i$ 번째 줄에 두 정수 $A_i$ , $B_i$ 가 주어진다. 이는 $W_i$ 가 $S_{A_i}$ 에서 $S_{B_i}$ 로 전달되는 네트워크임을 뜻한다. ( $i = 1, 2, \dots, M$ , $1 \le A_i < B_i \le N$ )

출력

최대한 간략화했을 때 남은 네트워크의 수를 출력한다.

예제3

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