← 返回题目列表

Codeforces · 2134/D

D. 滑动树

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

给你一棵树$$$^{\text{*}}$$$,其$$$n$$$顶点编号从$$$1$$$到$$$n$$$。您可以使用以下多步操作修改其结构,称为 滑动操作:

  1. 选择三个 不同 顶点 $$$a$$$、$$$b$$$ 和 $$$c$$$ 使得 $$$b$$$ 直接连接到 $$$a$$$ 和 $$$c$$$。
  2. 然后,对于 $$$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$$$) - 以最佳序列选择的第一个滑动操作的顶点。

如果第一次操作有多个有效选择,则可以输出其中任何一个。

示例

输入
复制

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

输出
复制

4 3 5
-1
-1
2 4 1

注意

第一个测试用例与问题陈述中提供的示例匹配。可以证明,我们不能使用少于 $$$2$$$ 操作将给定的树转换为路径图。

但是,我们可以使用 $$$2$$$ 操作将给定的树转换为路径图:最初,我们使用 $$$a=4$$$、$$$b=3$$$ 和 $$$c=5$$$ 执行操作,如示例所示。接下来,我们应用 $$$a=3$$$、$$$b=5$$$ 和 $$$c=6$$$ 的运算。之后,树就变成了路径图。第二个操作如下图所示。

因此,我们获得了操作总数最小化的滑动操作序列。但请注意,只有第一个操作必须在输出中;操作次数和第二次操作应 不 出现在输出中。

在第二个和第三个测试用例中,树已经是路径图,因此不需要任何操作。