HOLI  Holiday Accommodation
Nowadays, people have many ways to save money on accommodation when they are on vacation. One of these ways is exchanging houses with other people.
Here is a group of N people who want to travel around the world. They live in different cities, so they can travel to some other people's city and use someone's house temporary. Now they want to make a plan that choose a destination for each person. There are two rules should be satisfied:
 All the people should go to one of the other people's city.
 Two of them never go to the same city, because they are not willing to share a house.
They want to maximize the sum of all people's travel distance. The travel distance of a person is the distance between the city he lives in and the city he travels to. These N cities have N1 highways connecting them. The travelers always choose the shortest path when traveling.
Given the highways' information, it is your job to find the best plan, that maximum the total travel distance of all people.
Input
The first line of input contains one integer T (1 ≤ T ≤ 10), indicating the number of test cases.
Each test case contains several lines. The first line contains an integer N (2 ≤ N ≤ 10^{5}), representing the number of cities. Then the following N1 lines each contains three integers X, Y, Z (1 ≤ X, Y ≤ N, 1 ≤ Z ≤ 10^{6}), means that there is a highway between city X and city Y, and length of that highway.
You can assume all the cities are connected and the highways are bidirectional.
Output
For each test case in the input, print one line: "Case #X: Y", where X is the test case number (starting with 1) and Y represents the largest total travel distance of all people.
Example
Input: 2 4 1 2 3 2 3 2 4 3 2 6 1 2 3 2 3 4 2 4 1 4 5 8 5 6 5 Output: Case #1: 18 Case #2: 62
hide comments
divyn:
20210905 09:21:25
can someone explain how pigeonhole principle is being applied here? 

pantabhishek43:
20210829 09:57:55
don't use map instead use unordered_map


williams_sma2:
20210312 08:23:05
is this can be solved using dp? 

tech_runner:
20200928 21:41:29
Where to discuss on SPOJ about WA in code


coding_joshi26:
20200705 04:55:21
Common Mistakes done by me also


hetp111:
20191012 17:32:46
nice one... 

iamjacksparrow:
20190404 00:39:49
take visited array size 1e5+1( not 1e5 :( ) 

ankit0107verma:
20190103 13:39:35
Beware avoid using maps for visited and counting nodes in dfs ,use unordered map or array else you will see the wrath of TLE


ankitpriyarup:
20181210 17:32:45
After 3 WA finally AC :) 

riyuzaki251097:
20180822 11:54:54
great question learnt a lot , hint is to use pigeonhole theorem

Added by:  Bin Jin 
Date:  20111108 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  ACM/ICPC Regional Contest, Chengdu 2011 