Plants versus Zombies HD Super Pro is a game played not a grid, but on a connected graph G with no cycles (i.e., a tree). Zombies live on edges of the tree and chew through edges so that tree falls apart! Plants can be purchased and placed on vertices of the tree to protect the tree from falling apart. It is not possible to plant more than one plant on the same vertex. A plant protects one or more adjacent edges, depending on the strength and capabilities of the plant.
The Almanac offers you to buy any of three different types of plants:
The input starts with an integer T - the number of test cases (T <= 100). T cases follow, each starting with the integer N on the first line, the number of vertices in G (2 <= N <= 10,000). N-1 line follows, each containing two space separated integers u and v (0 <= u,v <= N-1, u ≠ v) - describing an edge.
For each test case, print on a separate line the minimum cost of protecting the tree, formatted like in the sample output.
2 2 0 1 3 0 1 1 2
$100 $175In the second case we can put a Split Pea on the vertex 1.