Problem I: Plants vs. Zombies HD Super Pro

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:

Your goal is to protect the tree from the Zombies by having every edge covered by at least one plant, and doing so spending the least amount of money. You can buy more than one of each type of plant, but you can only plant at most one plant on each vertex.

Input Format

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.

Output Format

For each test case, print on a separate line the minimum cost of protecting the tree, formatted like in the sample output.

Sample Input

0 1
0 1
1 2

Sample Output

In the second case we can put a Split Pea on the vertex 1.
Peter Høyer
ACPC 2011