#213361. [GCJ 2014 #1A] Full Binary Tree

A tree is a connected graph with no cycles.

A rooted tree is a tree in which one special vertex is called the root. If there is an edge between and in a rooted tree, we say that is a child of if is closer to the root than (in other words, the shortest path from the root to is shorter than the shortest path from the root to ).

A full binary tree is a rooted tree where every node has either exactly children or children.

You are given a tree with nodes (numbered from to ). You are allowed to delete some of the nodes. When a node is deleted, the edges connected to the deleted node are also deleted. Your task is to delete as few nodes as possible so that the remaining nodes form a full binary tree for some choice of the root from the remaining nodes.

The first line of the input gives the number of test cases, . test cases follow. The first line of each test case contains a single integer , the number of nodes in the tree. The following lines each one will contain two space-separated integers: , indicating that G contains an undirected edge between and .

For each test case, output one line containing "Case #: ", where is the test case number (starting from ) and is the minimum number of nodes to delete from to make a full binary tree.

样例输入 1

3
3
2 1
1 3
7
4 5
4 2
1 2
3 1
6 4
3 7
4
1 2
2 3
3 4

样例输出 1

Case #1: 0
Case #2: 2
Case #3: 1

Sample Explanation

In the first case, G is already a full binary tree (if we consider node as the root), so we don't need to do anything.

In the second case, we may delete nodes and ; then can be the root of a full binary tree.

In the third case, we may delete node ; then will become the root of a full binary tree (we could also have deleted node ; then we could have made the root).

Limits

• .
• Each test case will form a valid connected tree.

Small Dataset(9 Pts)

• Time limit: 60 3 seconds.
• .

Large dataset(21 Pts)

• Time limit: 120 10 seconds.
• .