15562번 - 네트워크

문제

우리의 회사에는 N개의 네트워크 시스템 S₁, S₂, ..., S_N와 이들을 연결하는 M개의 네트워크들 W₁, W₂, ..., 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 ≤ N, M ≤ 10⁶)

M줄 동안 두 숫자 A_i, B_i가 주어진다. 이는 W_i가 S_Ai와 S_Bi를 연결함을 뜻한다. (i = 1, 2, ..., M, 1 ≤ A_i < B_i ≤ N)

출력

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

제한

힌트