You are asked to build a highway from Taipei to Kaohsiung. Of course the length should be the shortest in economic concern. There may be several ways to build the shortest one. If that's the case, please build the highway, by selecting from the given roads, such that the number of sites adjacent to the highway is maximized.
More specifically, we assume that there are S sites and some R roads connecting two sites. Each site is assigned to a unique integer between 0 and S-1, and each road is of length 1. Please write a program to solve it.
There will be an integer N in the first line, indicating the number of test cases. For each test case there will be two integers, S and R, on their own line. In the following R lines each line contains two integers, xi and yi, denoting that there is a road between site xi and site yi. There may be empty lines between two test cases.
※Taipei is always assigned to 0, and Kaohsiung is always assigned to 1.
※There is always a path from Taipei to Kaohsiung.
※Some sites may be unreachable from Taipei.
※1 ≤ N ≤ 100
※2 ≤ S ≤ 400
※1 ≤ R ≤ 2000
For each test case, output the length of the highway, a whitespace, and the maximum number of adjacent sites. Output each case in a single line.
4 2 1 0 1 3 3 0 1 1 2 0 2 5 5 0 4 0 2 2 4 1 2 1 4 7 9 0 6 0 2 0 4 2 4 3 4 2 3 3 5 4 5 1 5
1 0 1 1 2 1 3 3
Migrated from old NTUJ.
2011 google code jam round 2
| No. | Testdata Range | Score |
|---|