给定一棵具有 $$$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$$$。
示例
输入复制
363 46 13 23 14 588 67 48 52 73 25 21 231 22 3
输出复制
1 2 2 3 41 2 2 2 3 4 51 2
注意
在第一个测试用例中,$$$k=1,2,\ldots,n-1$$$ 的可能解决方案如下: