J9 例题-4 平衡度

题目描述

考虑一棵树 $T$，其中 $N$ 个节点编号为 $1...N$ 。从树中删除任何节点都会生成一个森林：一个或多个树的集合。 将某个节点的平衡度定义为：如果从原树 $T$ 中，删除该节点而创建的森林中，最大树的那棵树的节点数量。 例如，对于如下的一棵树：

如果删除结点 $4$ 会产生两棵树，其成员结点为 ${5}$ 和 ${1,2,3,6,7}$ 。这两棵树中较大的树有五个结点，因此节点 $4$ 的平衡度为 $5$。 如果删除结点 $1$ 将生成一个由三棵大小相等的树组成的森林：${2,6}$、${3,7}$ 和 ${4,5}$。每个树都有两个结点，因此结点 $1$ 的平衡度是 $2$。

每个测试样例，都是一棵树，请计算具有最小平衡度的节点。如果多个节点具有相等的平衡度，则输出编号最小的节点。

输入格式

第一行输入包含单个整数 $t$，表示测试的数量，接下来 $t$ 组数据，表示每棵树进行测试：

对于一组测试数据，第一行包含一个整数 $N$，即树的节点个数。 接下来的 $N-1$ 行，每行包含两个整数，表示相邻的节点号，它们是树中某条边的情况（数据保证没有重复的边）。

输出格式

对于每个测试样例，打印一行包含两个整数，即具有最小平衡度的节点的编号以及该节点的平衡度。

样例输入

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

样例输出

1 2

样例分析

如上所述。

数据范围

对于 $100\%$ 的数据：$1 \le t \le 20$, $1 \le N \le 20000$。