2409: Centroid of a Tree

Given a tree T with N vertices, your task is calculating the number of the connected sub-tree of T, which has the same centroid as T.
In order to define the centroid, some integer value will be associated to every vertex. Let's consider the vertex k. If we remove the vertex k from the tree (along with its adjacent edges), the remaining graph will have only N-1 vertices and may be composed of more than one connected components. Each of these components is (obviously) a tree. The value associated to vertex k is the largest number of vertices contained by some connected component in the remaining graph, after the removal of vertex k. All the vertices for which the associated value is minimum are considered centroids.
A graph can have an arbitrary number of centroids. However,it can be proved that for trees, there are only two possibilities:
1. The tree has precisely one centroid.
2. The tree has precisely two centroids. In this case, the two centroids are adjacent.
Note that in case 2, we just consider that T has two centroids, you should only count the sub-tree which has the two same centroids as T.

The first line of the date is an integer T, which is the number of the text cases.
Then T cases follow each case starts of a number N descript above.
Then N-1 lines follow, each line contains two integers x and y, which means that there is a edge between x and y in tree T, you can assume that the index of T is from 1 to N.
1 <= T <= 50, 1 <= N <= 200,

For each case, output the case number first, then output the number of the connected sub-tree which has the same centroid as T.
Give your answer modulo 10007.

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

Case 1: 1
Case 2: 1
Case 3: 2
Case 4: 5
Case 5: 6