Description
Plants versus Zombies HD Super Pro is a game played not on 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:
- PEASHOOTERS: These are your first line of defense and can shoot peas along any one edge (of your choosing) adjacent to the vertex upon which it is placed. Cost: $100 per plant.
- SPLIT PEAS: These are hard working pea shooters and can shoot peas along any two edges (of your choosing) adjacent to the vertex upon which it is placed. Cost: $175 per plant.
- STARFRUIT: Having just visited the dentist, a STARFRUIT is very upset and shoots stars along all edges adjacent to the vertex upon which it is placed. Cost: $500 per plant.
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
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
For each test case, print on a separate line the minimum cost of protecting the tree, formatted like in the sample output.