← 返回题目列表

Codeforces · 2108/E

E. 云杉纠纷

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

外面已经是炎热的四月,波利卡普认为这是最终拆除他几年前种下的云杉树的最佳时机。当他花了几个小时绕着云杉走来走去,积蓄力量时,他注意到了一些奇怪的事情:这棵云杉实际上是一棵树$$$^{\text{*}}$$$——而且不仅仅是任何一棵树,而是由一棵树组成的一棵树。 奇数 顶点数 $$$n$$$。此外,在 $$$n-1$$$ 的顶点上悬挂着圣诞装饰品,完全用 $$$\frac{n-1}{2}$$$ 不同的颜色绘制,每种颜色恰好绘制了两个装饰品。按照传统规定,剩下的顶点固定着树的顶部。

经过几天的心理准备,波利卡普终于开始拆除这棵云杉。首先,他取下了礼帽,并开始拆开一些树枝,突然一个自然的问题向他袭来:他怎样才能取下树的一个边缘并重新排列装饰物,以使相同颜色的装饰物之间的简单路径的长度之和尽可能大?

在此问题中,从树中删除边的定义如下:选择一对相邻顶点 $$$a$$$ 和 $$$b$$$ ($$$a \lt b$$$),然后从树中删除顶点 $$$b$$$ 并将 $$$b$$$ 的所有相邻顶点($$$a$$$ 除外)直接重新附加到$$$a$$$。

波利卡普在得到这个问题的答案之前无法继续拆除他的云杉。然而,检查所有可能的选择还需要他几年的时间。了解你在竞争性编程方面的经验后,他向你寻求帮助。但你能解决这个争端吗?

$$$^{\text{*}}$$$树是没有环的连通图。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个 奇数 number $$$n$$$ ($$$3 \le n \lt 2 \cdot 10^5$$$) — 树中的顶点数。

以下 $$$n-1$$$ 行描述了树,由相邻顶点对 $$$u$$$, $$$v$$$ ($$$1 \le u, v \le n, u \neq v$$$) 给出。

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

输出

对于每个测试用例,您需要输出两行。

在第一行中,输出一对顶点 $$$u$$$、$$$v$$$,即 Polycarp 将删除的边。

在下一行中,输出从 $$$0$$$ 到 $$$\frac{n-1}{2}$$$ 的 $$$n$$$ 个数字的数组 $$$c$$$,其中 $$$c[i]$$$ — 分配给顶点 $$$i$$$ 的正颜色编号。请注意 $$$c[\text{max}(u, v)]= 0$$$,因为该顶点已被删除。

示例

输入
复制

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

输出
复制

1 2
2 0 1 1 2
1 5
1 1 2 2 0
4 3
1 3 3 0 2 2 1

注意

考虑第一个测试用例。

删除连接顶点 $$$1$$$ 和 $$$2$$$ 的边。此后,顶点$$$2$$$将从树中删除,顶点$$$3$$$和$$$4$$$将连接到顶点$$$1$$$。

颜色顶点 $$$3$$$ 和 $$$4$$$ 使用第一种颜色,顶点 $$$1$$$ 和 $$$5$$$ 使用第二种颜色。相同颜色的装饰品之间的简单路径的长度之和等于 $$$2 + 2 = 4$$$。可以证明这个值是最大可能的。

在第二个和第三个示例中,路径长度的最大总和将分别为 $$$3$$$ 和 $$$9$$$。