79 - The 6th Zhejiang Provincial Collegiate Programming Contest - E
There was a large earthquake in Sichuan last May. All the things were ruined in that disaster, the buildings, the railways and the establishments.
In order to send the rescue materials to where the disaster was, the traffic had to be reconstructed first. But just after the earthquake, the government spent a lot of money propitiating the refugees and could not afford much on reconstruction. After investigating the remaining roads, the government decided to make one new road so that the maximum connected component would be maximized by this new road (in a connected component, each village has directed paths to any other villages). Now your task is to determine how the new road is to be constructed.
The first line of the input contains an integer T (T <= 50), indicating the number of cases.
The first line of each test case contains two integers N and M (2 <= N <= 50000, 0 <= M <= 500000), indicating the number of villages and the number of remaining roads. Each of the next M lines contains two integers Ai and Bi (1 <= Ai, Bi <= N), meaning that the i-th road is from village Ai to village Bi.
For each test case, first output an integer indicating the maximum number of villages to which one can go from any village. The second line contains two integers A and B indicating the two villages that the new road is connecting to. If there are several solutions leading to the same result, output the one that comes lexicographically first (as defined in Problem C).
1 5 4 1 3 2 3 3 4 3 5
3 4 1
Author: GUAN, Yao
Source: The 6th Zhejiang Provincial Collegiate Programming Contest