시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 58 27 9 81.818%

문제

치삼이는 축제를 맞아 가톨릭대학교에 건물옥상에서 다른 건물옥상으로 이동하는 워터슬라이드를 짓기로 했다!

가톨릭대학교의 건물은 총 N개로 이루어져 있으며, 편의상 1번 건물부터 N번 건물까지 있다고 하자.

이 건물들의 옥상과 옥상 사이에 미끄럼틀이 설치되어 있다면 미끄럼틀을 따라 연결된 건물옥상으로 물이 흐른다.

단 미끄럼틀은 방향이 정해져 있어 주어진 방향으로만 물이 흐를 수 있으며, 이동할 수 있는 모든 건물옥상으로 물이 흐른다.

예를 들어 1에서 2번으로 향하는 미끄럼틀이 있고, 2에서 3번으로 향하는 미끄럼틀이 있다면, 1번에 물을 붓는다면 2번과 3번 건물옥상에도 물이 흘러간다는 의미이다.

미끄럼틀의 설치는 모두 완료되었고, 내일이 축제이므로 치삼이는 이제 양동이를 구입해 물을 흘려보내 워터슬라이드를 완성하려고 한다!

양동이는 상상할수 없을 만큼 충분히 크기 때문에, 물을 부으면 미끄럼틀을 타고 흐를수 있는 모든 건물옥상으로 전달된다.

하지만 양동이가 너무 비싼 관계로 치삼이는 양동이의 구매를 최소화 하려고 한다.

여러분이 치삼이를 도와 최소 몇개의 양동이로 모든 건물옥상에 물을 흘려보낼 수 있는지 구해주자!

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 두 정수 N, M이 주어지며 두 수는 100,000을 넘지 않는다.

N은 건물의 개수를, M은 미끄럼틀의 개수를 나타낸다.

건물 옥상들의 번호는 1과 N 사이의 정수다. 다음 M개의 줄에는 각각 두 정수 x, y가 주어지는데, 이는 x번 건물 옥상에서 y번 건물 옥상으로 향하는 미끄럼틀이 설치되어있음을 뜻한다.

출력

각 테스트 케이스마다 한줄에 최소 양동이의 개수인 정수 하나를 출력한다.

예제 입력 1

1
4 3
1 2
2 1
3 1

예제 출력 1

2

예제 입력 2

1
10 4
6 1
9 7
9 7
4 3

예제 출력 2

7