34068번 - 오디션

알고 있는가? 선린 1호관 엘리베이터의 비밀을. 매일 밤, 그 엘리베이터를 타면 지하로 향하는 길이 열린다. 그리고 그곳에선 아무도 모르게, 비밀의 오디션이 개최된다.

이 오디션엔 총 $N$명의 참가자가 있다. 오디션의 방식은 간단하다. 두 사람이 결투를 벌이고, 이긴 사람은 $1$점을 얻는다. 매번 한 명은 승자, 한 명은 패자로 결정되고 무승부는 없다. 지금까지 총 $M$번의 결투가 진행되었고, 그 결과는 모두 기록되어 있다.

당신은 참가자들의 순위를 $1$위부터 $N$위까지 정확히 결정하고 싶다. 단, 동점자가 있다면 순위는 결정되지 않는다. 참가자들의 순위를 모두 결정짓기 위해 추가로 치러야 할 결투의 최소 횟수는 몇 번인가?

첫째 줄에 참가자의 수 $N$과 지금까지 진행된 결투의 횟수 $M$이 공백으로 구분되어 주어진다.

둘째 줄부터 $M$개의 줄에 걸쳐, $i+1(1\leq i\leq M)$번째 줄에는 $i$번째 결투의 결과가 주어진다. 각 줄에는 두 사람의 번호 $A_i,B_i$가 공백으로 구분되어 주어지며, 이는 $A_i$가 $B_i$와의 결투에서 승리했다는 뜻이다.

참가자들의 순위를 모두 결정짓기 위해 추가로 치러야 할 결투의 최소 횟수를 출력하라.

• 주어지는 모든 수는 정수이다.
• $2\leq N\leq 200\, 000$
• $0\leq M\leq 200\, 000$
• $1\le A_i,B_i\le N$ ($1\le i\le M$)
• $A_i\ne B_i$ ($1\le i\le M$)

정답이 32비트 정수 범위를 넘을 수 있으므로, C/C++에서는 long long, Java에서는 long과 같은 자료형을 사용하는 것을 권장한다.