← 返回题目列表

Codeforces · 1406/C

C. 链接切割质心

中文机器翻译题面 查看原题

钓鱼王子爱树,尤其爱只有一个质心的树。树是一个没有环的连通图。

仅当您切割该顶点(删除它并删除该顶点的所有边)时,该顶点才是树的质心,剩余图的最大连通分量的大小是尽可能小的。

例如,下面这棵树的质心是$$$2$$$,因为当你切割它时,剩余图的最大连通分量的大小是$$$2$$$并且不能更小。

然而,在某些树中,可能有多个质心,例如:

顶点 $$$1$$$ 和顶点 $$$2$$$ 都是质心,因为切割它们之后最大连通分量的大小为 $$$3$$$。

现在钓鱼王子有一棵树。他应该砍掉树的一条边(意思是去掉这条边)。之后,他应该添加一条边。这两个操作之后的结果图应该是一棵树。他可以添加他切割的边缘。

他希望生成的树的质心是唯一的。帮助他找到任何可能的方法来进行手术。可以证明,至少有一种这样的方式总是存在的。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3\leq n\leq 10^5$$$) — 顶点数。

接下来的 $$$n-1$$$ 行包含两个整数 $$$x, y$$$ ($$$1\leq x,y\leq n$$$)。这意味着存在一条连接顶点 $$$x$$$ 和 $$$y$$$ 的边。

保证给定的图是一棵树。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,打印两行。

在第一行中打印两个整数 $$$x_1, y_1$$$ ($$$1 \leq x_1, y_1 \leq n$$$),这意味着你切割了顶点 $$$x_1$$$ 和 $$$y_1$$$ 之间的边。应该存在连接顶点 $$$x_1$$$ 和 $$$y_1$$$ 的边。

在第二行中打印两个整数 $$$x_2, y_2$$$ ($$$1 \leq x_2, y_2 \leq n$$$),这意味着在顶点 $$$x_2$$$ 和 $$$y_2$$$ 之间添加边。

这两个操作之后的图应该是一棵树。

如果有多个解决方案,您可以打印任何一个。

示例

输入 #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$$$ 成为唯一的质心。