Second International  Programming Contest
March 28, 2004, Blagoevgrad, Bulgaria
Problem F
Optimization
A multiprocessor machine has to perform a set of N tasks. For each task we know a set of the tasks that should be finished before this task can start. Each processor can perform one task for one second (or can stay unused for one second). If we have unlimited number of processors, calculate the minimal time T that is required for all the tasks to be performed. Find the minimal possible number of processors that are required to perform all the tasks in time T.
Example
We have N=10 tasks. We know that task 4 depends on task 1, task 5 depends on task 2, task 6 depends on task 3, task 6 depends on task 4, task 5 depends on task 4, and task 6 depends on task 5. The minimal possible time T is 4. The minimal number of processors P for performing all the tasks in time 4 is 3. A possible allocation of the processors is following:
	processor 1	processor 2	processor 3	
step 1	3	1	2	
step 2	4	7	9	
step 3	5	8	-	
step 4	6	10	-	
Input data
The input data is given in the standard input. On the first line is given the number of the test cases K (1 <= K <= 20) that your program should solve. Each of the K test cases that follow is described as follows:
Line 1: contains the number of tasks N (1 <= N <= 2000).
Line 2: contains single integer M – the number of task dependencies.
Lines 3…M+2: Each of them contains two numbers A and B separated by a space denoting that task A should be performed before task B.
Output data
The standard output file should contain K lines. Each of these lines should correspond to one test case from the input file and should contain the calculated numbers T and P separated by a space.
Sample input file                               Sample output file
2                             2 3
5                             4 3
3
1 3
2 3
5 3
10
6
1 4
2 5
3 6
4 6
4 5
5 6