钓鱼王子爱树,尤其爱只有一个质心的树。树是一个没有环的连通图。
仅当您切割该顶点(删除它并删除该顶点的所有边)时,该顶点才是树的质心,剩余图的最大连通分量的大小是尽可能小的。
例如,下面这棵树的质心是$$$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$$$ 成为唯一的质心。