주식 추적

작년에 은행 현금 위기를 해결하려고 내가 제안했던 방법이 경제 위기 전체를 해결하지는 못했다는 사실을 인정한다. 알고 보니 회사들은 애초에 현금을 그렇게 많이 가지고 있지 않았다. 회사가 보유한 것은 대부분 다른 회사의 지분, 즉 주식이다.

한 회사가 다른 회사의 주식을 보유하는 것은 흔하고 허용되는 일이다. 문제를 복잡하게 만드는 것은 두 회사가 동시에 서로의 주식을 보유하는 경우다. 잠깐 생각해 보면, 이때 각 회사는 (간접적으로) 자기 자신의 주식을 지배하게 된다.

이제 새로운 시장 규제가 시행된다. 어떤 회사도 직접적이든 간접적이든 자기 자신의 주식을 지배해서는 안 된다. 예를 들어 회사 $A$가 $B$의 주식을 사고, $B$가 $C$의 주식을 사고, 그다음 $C$가 $A$의 주식을 사는 상황을 생각해 보자. 앞의 두 거래는 허용되지만, 세 번째 거래는 세 회사가 모두 자기 자신의 주식을 지배하게 만들므로 거부되어야 한다.

프로그램에는 모든 매수 거래가 시간 순서대로 주어진다. 어떤 회사가 자기 자신의 주식을 지배하게 만들 수 있는 거래는 거부하고, 그 외의 모든 거래는 승인해야 한다. 거부된 거래의 수를 구하여라.

입력은 하나 이상의 테스트 케이스로 이루어진다. 각 테스트 케이스는 $T + 1$개의 줄로 주어진다. 첫 줄에는 두 양의 정수 $N$과 $T$가 주어진다. 여기서 $N$은 회사의 수이고 ($0 < N \le 234$), $T$는 거래의 수이다 ($0 < T \le 100000$). 이어지는 $T$개의 줄에는 각각 매수 거래가 하나씩 주어지며, 두 정수 $A$와 $B$ ($0 < A, B \le N$)로 표현된다. 이는 회사 $A$가 회사 $B$의 주식을 사려 한다는 뜻이다.

입력의 마지막 줄에는 두 개의 0이 주어진다.

각 테스트 케이스마다 다음 한 줄을 출력한다.

k. R

여기서 $k$는 테스트 케이스 번호(1부터 시작)이고, $R$은 거부되어야 하는 거래의 수이다.