Full Binary Tree (Large)

A tree is a connected graph with no cycles.

A rooted tree is a tree with one vertex chosen as the root. In a rooted tree, if there is an edge between $X$ and $Y$ and the shortest path from the root to $X$ is shorter than the shortest path from the root to $Y$, then $Y$ is a child of $X$.

A full binary tree is a rooted tree in which every vertex has exactly 2 children or exactly 0 children.

You are given a tree $G$ with $N$ vertices, numbered $1$ through $N$. You may delete some of the vertices, and deleting a vertex also deletes every edge attached to it. Delete as few vertices as possible so that the vertices left over form a single full binary tree for some choice of root among them.

The first line contains the number of test cases $T$. The first line of each test case contains one integer $N$, the number of vertices of the tree. Each of the next $N-1$ lines contains two space separated integers $X_i$ and $Y_i$, meaning that $G$ has an undirected edge between $X_i$ and $Y_i$.

Limits

• $1 \le T \le 100$
• $2 \le N \le 1000$
• $1 \le X_i, Y_i \le N$
• The edges of every test case form a connected tree.

For each test case print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the minimum number of vertices you have to delete from $G$ to leave a full binary tree.

In the first sample test case $G$ is already a full binary tree with vertex 1 as the root, so nothing has to be deleted.

In the second sample test case, deleting vertices 3 and 7 leaves a full binary tree rooted at vertex 2.

In the third sample test case, deleting vertex 1 leaves a full binary tree rooted at vertex 3. Deleting vertex 4 and rooting at vertex 2 works too.