数据结构基础

【题目描述】平衡（banance）POJ 1655

考虑一个具有N（1≤N≤20000）个结点，编号为（1~N）的树T，从树T删除任何结点都会生成一个森林：一个或多棵树的集合。从树中删除某个结点后，森林中最大树的结点个数即为该结点的平衡值，例如图4.65所示的一棵树。

图4.65

 

删除结点4后产生两棵树，分别为{5}和{1，2，3，6，7}，这两棵树中最大的子树结点有5个，所以结点4的平衡值为5，又如删除结点1后产生三棵树，分别为{2，6}，{3，7}和{4，5}，这三棵树的结点数均为2，所以结点1的平衡值为2。

现在的任务是：对于每一个输入的树，输出平衡值最小的结点编号，如果有相同的平衡值，输出最小编号的结点。

【输入格式】

输入第一行是一个整数t（1≤t≤20），表示有t组测试数据，每组数据第一行为一个整数N（1≤N≤20000），表示树的结点数，随后N－1行，每行两个数A和B，表示A和B有边相连。

【输出格式】

输出两个数，即平衡值最小的结点编号和平衡值。

【输入样例】

1

7

2 6

1 2

1 4

4 5

3 7

3 1

【输出样例】

1 2