The Fastest Runner Ms. Zhang

Ms. Zhang is a journalist from Hong Kong, and she runs very very fast, so every one calls her “The fastest runner”. There are n cities (numbered from 1 to n) and n roads in the country, the roads are undirected. It costs 1 unit of time to go through each road. There exists at least one path between any pair of cities. Now Ms. Zhang can start her interview in city S, visit all of the n cities and finish her interview in city T. Since Ms. Zhang’s interview is simple and naive, the interview does not cost any time. Can you help Ms. Zhang to find the optimal S and T that minimise the total traveling time of Ms. Zhang? If there are multiple optimal solutions, output the solution with the smallest S. If there are still multiple solutions, output the solution with the smallest T.

The first line contains only one integer T ($T\leq 40$), which indicates the number of test cases.

Each test case contains n + 1 lines.

The first line contains one integer $1\leq n\leq 10^5$.

In the next n lines, each line contains two integers x and y indicating there is a road between city x and city y.

It is guarenteed that there does not exist a road connecting one city to itself or two roads connecting the same pair of cities.

For each test case, output one line “Case #x: t S T ”, where x is the case number(starting from 1),t is the minimal total traveling time, S and T are the index of starting and ending city.

1
10
7 1
5 3
4 5
8 9
6 4
8 6
2 7
10 3
4 1
9 7

Case #1: 10 1 10

2016中国大学生程序设计竞赛（长春）-重现赛