#1101 소공전

41  10 s   256 MB  

Description

숭실대학교에서는 올해도 어김없이 10월 달에 소프트웨어 공모전(일명 소공전)이 열린다.
그래서, 많은 학생들은 소공전에 입상하기 위하여 여름방학 동안 밤새 프로젝트에 몰두하곤 한다. 정희도 이번 소공전에 참가하려는 학생중의 한 명이다. 그러나, 정희는 여름방학 동안 즐거운 휴가를 보낸 덕분에, 소공전 준비를 전혀 하지 못했다. 시간이 얼마 남지 않았기 때문에, 정희는 어떻게 하면 프로젝트를 빨리 완성할 수 있을지 연구하기 시작했다. 그 결과, 프로젝트를 여러 개의 작은 작업(task)으로 나누어서 진행하면 더 효과적일 것이라는 결론 을 내렸다. 프로젝트를 여러 개의 작업으로 나누고, 각 작업들의 흐름도를 그려본 후, 어떤 작업들은 서로 의존성이 없어서 동시에 진행할 수 있지만, 어떤 작업들은 다른 작업들이 끝
나야 시작할수 있음을 알았다. 정희는 작업 흐름도를 완성한 후, 프로젝트가 몇 일만에 끝 날 수 있을지 계산해 보려고 한다. 과연 정희는 몇 일만에 프로젝트를 완성할 수 있을까?

여기서 다음과 같은 조건을 항상 만족한다고 가정한다.
1) 모든 작업들은 마치는데 균일하게 하루가 걸린다.
2) 정희의 프로젝트를 도울 수 있는 친구들이 무한이 많다. 따라서 서로 의존성이 없는 작업들은 모두 동시에 진행할 수 있다
3) 작업들간의 의존성이 cycle을 이루지 않는다. 예를 들어, A -> B, B -> C, C -> A 와 같은 경우는 없다. (A -> B는 작업 B를 시작하기 위해서는 작업 A가 먼저 끝나야 한다는 의미이다.)

예를 들어, A, B, C, D, E, F, G라는 작업들이 위 그림과 같은 의존성을 가지고 있다고 하자.
D라는 작업을 시작하기 위해서는 B와 C작업을 먼저 끝내야 한다. C작업을 시작하기 위해서 는 A, B, E작업을 끝내야 하고, B작업을 시작하기 위해서는 A작업을 끝내야 한다. 그러나, A와 E같은 경우나, B와 F같은 경우는 서로 의존성이 없으므로 동시에 수행할 수 있다. 위와 같은 경우, 첫째 날 (A, E, F)를 수행하고, 둘째 날 (B, G)를 수행하고, 셋째 날 (C)를 수행하고, 넷째 날 (D)를 수행할 수 있다. 따라서 4일만에 프로젝트를 완성할 수 있다.

Input

입력의 첫 줄에는 테스트케이스의 개수 T (1 ≦ T ≦ 100)가 주어진다. 이어서, T개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄에는 작업의 개수 N (1 ≦ N ≦ 1,000)과 의존성 정보의 개수 M (0 ≦ M ≦ 499,500)이 주어진다. 각각의 작업은 1에서부터 N까지의 수 중 하나로 나타내기로 한다. 이어서 M줄에 걸쳐서 작업들의 의존성 정보가 나온다. 각 의존성 정보는 한 줄에 걸쳐서 한 쌍의 정수 p, q (1 ≦ p, q ≦ N)가 들어오고, 작업 q가 시작하기 위해서는 작업 p가 먼저 끝나야 한다는 의미이다.

Output

각 테스트 케이스에 대해서 몇 일만에 프로젝트를 완성할 수 있는지를 한 줄로 출력한다.

Sample Input

Sample Output

3
7 7
1 2
1 3
2 3
3 4
2 4
5 3
6 7
3 2
1 2
2 3
1 0
4
3
1