Time Limit: 1s
Memory Limit: 128MB
도미노는 굉장히 재미있는 게임이다. 한 도미노를 쓰러트리면 그 뒤에 세워진 도미노가 함께 부딪혀 쓰러진다는 성질을 이용해서 도미노들을 배치하고, 최종족으로 쓰러트리면서 노는 게임이다. 예쁘게 만들어놓은 도미노가 쓰러지는 것을 보고있으면 괜시리 기분이 좋아진다.
여기 도미노가 어떻게 세워져있는지에 대한 정보가 주어져있다. 최소 몇개의 도미노를 손으로 쓰러트렸을 때, 최종적으로 모든 도미노가 쓰러지게 되는지 구해보자.
입력에 첫번째 줄에는 테스트케이스의 개수 T가 주어진다.
각 테스트케이스마다 100,000을 넘지 않는 2개의 정수 n, m 이 주어진다. n은 도미노의 개수이고 m은 도미노의 관계의 개수를 나타낸다.
그 이후 m개의 줄에 걸쳐 2개의 정수 x y가 주어진다. (1 ≤ x,y ≤ n) 이는 x번 도미노가 쓰러진 경우 y번 도미노가 쓰러진다는 것을 의미한다.
각 테스트케이스마다 한줄에 하나씩 모든 도미노가 쓰러지기 위해 손으로 쓰러트릴 필요가 있는 도미노의 최소 개수를 출력하자.
1 3 2 1 2 2 3
1