#2560 소공전

10 s   64 MB  

Description

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

여기서 다음과 같은 조건을 항상 만족한다고 가정한다.

1) 모든 작업들은 마치는데 균일하게 하루가 걸린다. 2) 정희의 프로젝트를 도울 수 있는 친구들이 무한이 많다. 따라서 서로 의존성이 없는 작업들은 모두 동시에 진행할 수 있다 3) 작업들간의 의존성이 cycle을 이루지 않는다. 예를 들어, A

Input

입력은 표준입력(standard 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

출력은 표준출력(standard 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

HINT

입력을 받을 때, scanf()를 사용하는 것을 적극 추천합니다 :)

Source

2007 Soongsil University Campus Programming Contest, test data : Kogle