Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3206
Disaster Area Reconstruction

Time Limit: 10 Seconds      Memory Limit: 32768 KB

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.

NOTICE that:

  • Each road is one-way, i.e. you can only go from one end of the road to the other end, but can not go in the opposite direction.
  • No road is built from and to the same village, since it would be useless. But there could be more than one road from one village to another since this can enlarge the traffic capability between these two villages.


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).

Sample Input

5 4
1 3
2 3
3 4
3 5

Sample Output

4 1

Author: GUAN, Yao
Source: The 6th Zhejiang Provincial Collegiate Programming Contest
Submit    Status