给你一棵树$$$^{\text{*}}$$$,其$$$n$$$顶点编号从$$$1$$$到$$$n$$$。您可以使用以下多步操作修改其结构,称为 滑动操作:
- 选择三个 不同 顶点 $$$a$$$、$$$b$$$ 和 $$$c$$$ 使得 $$$b$$$ 直接连接到 $$$a$$$ 和 $$$c$$$。
- 然后,对于 $$$b$$$ 的每个邻居 $$$d$$$ (不包括 $$$a$$$ 和 $$$c$$$),删除 $$$b$$$ 和 $$$d$$$ 之间的边,并将 $$$d$$$ 直接连接到 $$$c$$$。
例如,下图说明了此操作,最左边的树中 $$$a = 4$$$、$$$b = 3$$$ 和 $$$c = 5$$$。
可以证明,经过滑动操作后,得到的图仍然是一棵树。
你的任务是找到一系列滑动操作,将树转换为路径图$$$^{\text{†}}$$$,而 最小化 操作总数。你只需要输出 第一次滑动操作 如果需要至少一项操作,则以最佳顺序 。可以证明,可以使用有限次数的操作将树转换为路径图。
$$$^{\text{*}}$$$树是没有环的连通图。
$$$^{\text{†}}$$$路径图是一棵树,其中每个顶点的度数最多为$$$2$$$。请注意,只有 $$$1$$$ 顶点且没有边的图也是路径图。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
以下 $$$n-1$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$) — 第 $$$i$$$ 条边的末端。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例:
- 如果不需要任何操作(即输入树已经是路径图),则输出$$$-1$$$。
- 否则,输出三个 不同 整数 $$$a$$$、$$$b$$$ 和 $$$c$$$ ($$$1 \le a,b,c \le n$$$) - 以最佳序列选择的第一个滑动操作的顶点。
如果第一次操作有多个有效选择,则可以输出其中任何一个。
示例
输入复制
464 33 53 11 23 6121 255 42 34 21 4
输出复制
4 3 5 -1 -1 2 4 1
注意
第一个测试用例与问题陈述中提供的示例匹配。可以证明,我们不能使用少于 $$$2$$$ 操作将给定的树转换为路径图。
但是,我们可以使用 $$$2$$$ 操作将给定的树转换为路径图:最初,我们使用 $$$a=4$$$、$$$b=3$$$ 和 $$$c=5$$$ 执行操作,如示例所示。接下来,我们应用 $$$a=3$$$、$$$b=5$$$ 和 $$$c=6$$$ 的运算。之后,树就变成了路径图。第二个操作如下图所示。
因此,我们获得了操作总数最小化的滑动操作序列。但请注意,只有第一个操作必须在输出中;操作次数和第二次操作应 不 出现在输出中。
在第二个和第三个测试用例中,树已经是路径图,因此不需要任何操作。