Don Seliari gives his right hand Tommas Angelo (Tommy) an important job to guard his territory. The mafia territory consists of n cities. And the cities are connected to each other in such a way that there is exactly one path from any city to another. Tommy has exactly n mafia boys to guard the cities. Initially the mafia boys are resting randomly at the n cities. Tommy wants every city to be guarded by the mafia boys. This is to be accomplished by a sequence of moves; each move consists of moving one mafia boy to the adjacent city. What is the minimum number of moves required so that every city is guarded?
Input
Input starts with an integer T (≤ 10), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 10000). Each of the next n line contains at least three numbers which are: v the number of a city, followed by the number of mafia boys placed at city v followed by a number d which is the number of cities adjacent of v, followed by d numbers giving the adjacent cities of v. Amongst the cities, one city is chosen as root, and for any city all its adjacent cities are listed except the one that connects it (through a path) to the root city.
Output
For each case, print the case number and the minimum number of moves required for the mafia boys to guard all cities.
Sample
Sample Input | Sample Output |
---|---|
2 9 1 2 3 2 3 4 2 1 0 3 0 2 5 6 4 1 3 7 8 9 5 3 0 6 0 0 7 0 0 8 2 0 9 0 0 9 1 0 3 2 3 4 2 0 0 3 0 2 5 6 4 9 3 7 8 9 5 0 0 6 0 0 7 0 0 8 0 0 9 0 0 | Case 1: 7 Case 2: 14 |