Description

Given a tree with $n$ vertices, labeled $1 \sim n$, count how many distinct connected subtrees have the same centroid as the original tree.

A tree on $n$ vertices is a minimally connected graph on $n$ vertices. It obviously has $n-1$ edges. If you remove any one of these $n-1$ edges, the original graph becomes disconnected. Between any two vertices there is a unique path.

For a tree, the centroid is defined as follows: after deleting a vertex $i$, if there are $k$ connected components left, define $d(i)$ to be the maximum number of vertices among these components. A centroid is a vertex $i$ that minimizes $d(i)$.

Based on this definition, a tree may have one or two centroids. The connected subtrees required in this problem must have exactly the same centroid labels and the same number of centroids as the original tree.

Find how many connected subtrees in the given tree have the same centroid as the original tree. Output the result $\bmod 10007$.

Input Format

The first line contains a positive integer $Q$, the number of test cases.

For each test case, first read an integer $n$ ($0 < n \le 200$), the number of vertices in the tree. Then read $n-1$ lines, each containing two integers $x, y$ ($1 \le x, y \le n$), indicating that there is an edge between vertices $x$ and $y$. All vertices are labeled $1 \sim n$.

Output Format

First output the test case index, then output the number of connected subtrees that satisfy the condition. Since this number can be large, you only need to output this number $\bmod\ 10007$. See the output example and strictly follow its format.

3
2
1 2
3
1 2
2 3
5
1 2
1 3
2 4
2 5

Case 1: 1
Case 2: 2
Case 3: 6

Hint

For $100\%$ of the testdata, $1 \le Q \le 50$, $1 \le n \le 200$.

Translated by ChatGPT 5