题目描述

给定一棵节点数为 n 的树 ， 删一条边然后加上一条边 ， 使得该树的重心唯一 。（删掉的边和加上的边可以是同一条）

输入格式

第 1 行一个正整数 T ， 表示有 T 组测试数据 ， 其中 1≤T≤10^4。 对于每组测试数据 。 第 1 行一个正整数 n ， 表示该树有 n 个节点 ， 其中 3≤n≤10^5。 第 2 行到第 n 行每行两个正整数 x,y ， 表示 x 到 y 有无一条无向边 ， 其中 1≤x,y≤n 。

输出格式

对于每一组测试数据 。 第 1 行两个正整数 x1,y1， 表示删的边的端点为 x1,y1。 第 2 行两个正整数 x2,y2， 表示连的边的端点为 x2,y2。

样例

输入样例 1

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

输出样例 1

1 2
1 2
1 3
2 3

输入样例 2

1
5
1 2
2 3
3 4
4 5

输出样例 2

1 2
1 2

输入样例 3

1
4
1 2
2 3
3 4

输出样例 3

2 1
3 1

提示

数据范围：对于每个测试点，保证 ∑n≤10^5。