1406C. C. Link Cut Centroids

CF1406C. Link Cut Centroids

时限: 1 秒 | 内存: 512 MB | 输入: 标准输入 | 输出: 标准输出

题意

给定一棵节点数为 $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$、$y_1$。

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

限制与约定

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

样例输入 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$ 和 $3$ 的边并添加连接结点 $2$ 和 $3$ 的边之后，结点 $2$ 成为唯一重心。