문제
블록들을 적절한 간격을 유지하여 일렬로 늘어세운다.
그리고 블록 하나를 넘어뜨리면 그 블록이 넘어지며
다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러진다.
잘 아는 것처럼 이와 같은 것을 도미노라 한다.
하지만 이따금씩 도미노가 다른 블록을 넘어뜨리지 못하게 배치되어 있다면,
우리는 다음 블록을 수동으로 넘어뜨려야 한다.
이제 각 도미노 블록의 배치가 주어진다.
구조상 어느 하나의 블록을 넘어뜨려 모든 블록들이 쓰러지지 않을 수도 있다.
모든 블록을 넘어뜨리기 위해 손으로 넘어뜨려야 하는 블록의 최소 개수를 구해보자.
입력
첫 행에 테스트 케이스의 개수가 주어진다.
각 테스트 케이스의 첫 번행에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다.
N은 도미노의 개수를, M은 관계의 개수를 나타낸다.
도미노 블록의 번호는 1과 N 사이의 정수다.
다음 M개의 줄에는 각각 두 정수 x, y가 주어지는데, 이는 x번 블록이 넘어지면 y번 블록도 넘어짐을 뜻한다.
그 반대의 경우는 성립하지 않는다.
출력
각 테스트 케이스마다 한 줄에 정수 하나를 출력한다.
정답은 손으로 넘어뜨려야 하는 최소의 도미노 블록 개수이다.
예제
1
3 2
1 2
2 3
1
태그
출처
Waterloo's local Programming Contests 27 September, 2008 D번
로그인해야 코드를 작성할 수 있어요.