题目背景

原题链接

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

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

输入格式

第 $1$ 行一个正整数 $T$ ， 表示有 $T$ 组测试数据 ， 其中 $1\le T\le10^4$

对于每组测试数据 。

第 $1$ 行一个正整数 $n$ ， 表示该树有 $n$ 个节点 ， 其中 $3\le n\le 10^5$ 。

第 $2$ 行到第 $n$ 行每行两个正整数 $x,y$ ， 表示 $x$ 到 $y$ 有无一条无向边 ， 其中 $1\le x,y\le n$ 。

输出格式

对于每一组测试数据 。

第 $1$ 行两个正整数 $x_1,y_1$ ， 表示删的边的端点为 $x_1,y1$ 。

第 $2$ 行两个正整数 $x_2,y_2$ ， 表示连的边的端点为 $x_2,y_2$ 。

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

1 2
1 2
1 3
2 3

限制与约定

对于每个测试点，保证 $\sum{n}\le10^5$。

提示

请注意，您可以在剪下的边上添加相同的边。

在第一个测试案例中，切割并添加相同的边后，顶点 $2$ 仍然是唯一的中心点。

在第二个测试案例中，切掉顶点 $1$ 和 $3$ 之间的边并添加顶点 $2$ 和 $3$ 之间的边后，顶点 $2$ 成为唯一的中心点。