Given a graph, we define “proper coloring” as coloring of the graph nodes in such way that no two adjacent nodes have the same color. If we map each color to a positive integer, we can calculate the sum of all colors assigned to the graph. In this problem you will be given a tree (connected graph with no simple loops). Can you determine what the minimum color sum can be achieved when the tree is properly col- ored? (Image to the right shows a proper col- oring of the second example tree with sum=11) Input The input file consists of several test cases. Each test case starts with n (1 ≤ n ≤ 10000), the number ofnodesinthetree. Nextnlineswillbeoftheform“u: v1 v2 ... vk”whereuistherootofa subtree and vi’s are its children (0 ≤ u, vi ≤ n − 1). Every test case will be followed by a blank line. Input ends with a case n = 0, which should not be processed. Output For each test case print the minimum sum of colors that can be achieved by some proper coloring of the tree. Sample Input 2 0: 1: 0 8 0: 1 2 3 1: 4 5 2: 3: 6 7 4: 5: 6: 7: 0 Sample Output 3
2/2 11