What is a tree?
A tree is a bidirectional connected graph with no cycle.
In a tree, we can create exactly one cycle if we connect any two nodes by an edge. Professor Ratman thinks that the cycle has holy powers. So the cost of such one cyclic graph is the total distance from all the nodes to any node of the cycle. Professor Ratman wants to determine the minimum cost given that you can connect any two nodes of the tree.
So you have to minimize
Suppose, we have the following tree:
If we connect 2 and 6 and make a cycle, then the cost would be 1 + 1 + 2 = 4.
But, if we connect 4 and 6, the cost will be, 1 + 1 = 2, which is the minimum cost in this case.
Your job is to find the minimum cost of creating one cycle.
The first line will contain an integer , the number of test cases.
For each test case, the first line contains , the number of nodes in the tree.
Next lines will describe the tree. Each line will contain two space-separated integers and indicating that there is a bidirectional edge between and .
It is guaranteed that the input is a valid tree and the sum of over all test cases will not exceed , that means .
For each test case, print “Case X: Y” where “X” indicates the case number and “Y” indicates the minimum cost for the given case.
1 6 1 5 5 2 5 6 3 5 3 4
Case 1: 2