← 返回题目列表

Codeforces · 2165/E

E. 彩虹分行

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

给定一棵具有 $$$n$$$ 个顶点的树,您需要为每条边分配一种颜色。定义 不便 指定的 作为任意两个顶点之间的路径上的最大颜色数。

您需要分配 正是 $$$k$$$ 不同颜色(每种颜色必须至少出现一次)到边缘,同时最小化 作业的 不便 指定的 。

请计算最小值 不便 指定的 对于所有 $$$k=1,2,\ldots,n-1$$$。

输入

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

输入的第一行包含一个正整数 $$$n$$$ ($$$3\le n\le3\cdot10^5$$$) — 顶点数。

接下来的 $$$n-1$$$ 行每行包含两个正整数 $$$u_i,v_i$$$ ($$$1\le u_i,v_i\le n$$$) - 表示顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间有一条边。

保证输入中的边形成一棵树。

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

输出

对于每个测试用例,打印一行包含 $$$n-1$$$ 整数。第 $$$i$$$ 个整数表示最小值 不便 指定的 $$$k=i$$$。

示例

输入
复制

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

输出
复制

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

注意

在第一个测试用例中,$$$k=1,2,\ldots,n-1$$$ 的可能解决方案如下: