平衡行为

题目描述

考虑一棵有 $N（1 <= N <= 20,000$）个节点的树 $T$，节点编号为 $1...N$。从树中删除任意一个节点会产生一片森林：一个或多个树的集合。定义一个节点的平衡度为从树 T 中删除该节点后形成的森林 T 中最大树的大小。

例如，考虑下面的树：

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

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

输入

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

输出

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

样例输入

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

样例输出

1 2