#P1655. 平衡操作

题目描述

考虑一棵有$N$（$1 \leq N \leq 20,000$）个节点的树$T$，节点编号为$1$到$N$ 。从这棵树中删除任意一个节点都会得到一个森林：由一棵或多棵树组成的集合。将一个节点的平衡度定义为从树$T$中删除该节点后得到的森林中最大树的节点数量。

例如，考虑如下这棵树：

删除节点$4$会得到两棵树，其节点集合分别为$\{5\}$和$\{1,2,3,6,7\}$ 。这两棵树中较大的那棵有五个节点，因此节点$4$的平衡度为五。删除节点$1$会得到一个由三棵大小相等的树组成的森林：$\{2,6\}$、$\{3,7\}$和$\{4,5\}$ 。每棵树都有两个节点，所以节点$1$的平衡度为二。

对于每个输入的树，计算平衡度最小的节点。如果有多个节点的平衡度相等，输出编号最小的那个节点。

输入格式

输入的第一行包含一个整数$t$（$1 \leq t \leq 20$），表示测试用例的数量。每个测试用例的第一行包含一个整数$N$（$1 \leq N \leq 20,000$），表示节点数量 。接下来的$N - 1$行，每行包含两个用空格分隔的节点编号，它们是树中一条边的两个端点。每条边不会被列出两次，并且所有边都会被列出。

输出格式

对于每个测试用例，打印一行，包含两个整数，分别是平衡度最小的节点编号以及该节点的平衡度。

输入数据示例 1

1  
7  
2 6  
1 2  
1 4  
4 5  
3 7  
3 1  

输出数据示例 1

1 2  

来源

POJ Monthly--2004.05.15 IOI 2003 样题