[Home|Training|Problems|Contests|C Language] | [Login|Register] |

Problems Status Rank |
Problem 1123
Two Hospitals
Time Limit: 2000ms
Memory Limit: 65536kb Description
In the highland, people live in towns. There are roads between pairs of towns, so that all the towns are connected by paths. Because the roads are different in length and surface, each road has a constant traveling time. Now, the government wants to build two hospitals in two of these towns. Which two towns should be chosen to locate the two hospitals? Let t The principle for locating the two hospitals is that the maximum t Now, given the roads and their traveling time, it is your job to find the two towns to build the two hospitals. Fortunately, in our cases, the solution of the problem is unique. Input
The first line of input is an integer k, which is the number of cases. The following 2k lines contain k cases. In each case, the first line contains two integers N and E, which are the number of towns and the number of roads in this case.
All the towns in the case are labeled as 1, 2, ..., N. (2 <= N <= 500, N-1 <= E <= 2000).
The second line contains 3E integers, that is a list as u Output
For case, output the labels of the two towns in one line, with the smaller label in front.
Sample Input
1 5 8 1 2 6 1 3 2 1 4 4 3 5 4 2 5 2 2 4 3 1 2 4 4 4 1 Sample Output
1 2 |

University of Science and Technology of China

Online Judge for ACM/ICPC

Processed in 1.1ms with 1 query(s).

Online Judge for ACM/ICPC

Processed in 1.1ms with 1 query(s).