시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 110 45 31 50.820%

문제

우리의 회사에는 N개의 네트워크 시스템 S1, S2, ..., SN와 이들을 연결하는 M개의 네트워크들 W1, W2, ..., WM이 있다. 네트워크 시스템들은 우선순위가 있어 모든 네트워크는 우선순위가 높은 곳에서 낮은 곳으로만 전달된다. 즉, SA에서 SB로 전달되는 네트워크가 있다면 A < B 이다.

최근 이 네트워크 시스템이 너무 난잡해져 이를 정리하기로 했다. 이를 설명하자면, 시스템 SASBSC에 대해서 SA에서 SB로 전달되는 네트워크와 SB에서 SC로 전달되는 네트워크가 있다면 이 둘을 합쳐 SA에서 SC로 전달되는 네트워크로 간략화하는 것이다. 이 방식으로 간략화를 반복해서 최대한 네트워크의 수를 줄이고자 한다. 이 때, 남은 네트워크의 수를 구하여라.

입력

첫 번째 줄에 N와 M이 주어진다. (1 ≤ N, M ≤ 106)

M줄 동안 두 숫자 Ai, Bi가 주어진다. 이는 Wi가 SAi와 SBi를 연결함을 뜻한다. (i = 1, 2, ..., M, 1 ≤ Ai < Bi ≤ N)

출력

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

예제 입력 1

5 7
1 2
1 3
1 4
2 3
2 5
3 4
4 5

예제 출력 1

4

출처

Contest > 웰노운컵 > 제 1회 웰노운컵 B1번