﻿ Fuzhou University OnlineJudge ﻿
Problem 2142 Center of a Tree

## Problem Description

Given a tree T with N vertices, your task is calculating the number of the connected sub-tree of T, which has the same center as T.

Given a graph, the eccentricity of a vertex v is defined as the greatest distance from v to any other vertex. A center of a graph is a vertex with minimal eccentricity. A graph can have an arbitrary number of centers. However, Jordan (1869) has proved that for trees, there are only two possibilities:

1. The tree has precisely one center (centered trees).

2. The tree has precisely two centers (bicentered trees). In this case, the two centers are adjacent.

from wikipedia

Note that in case 2, we just consider that T has two centers, you should only count the sub-tree which has the two same centers as T.

## Input

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 described 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 <= 100, 1 <= N <=1000.

## Output

For each case, output the case number first, then output the number of the connected sub-tree which has the same center as T.