这个版本的问题与下一版本的不同之处仅在于 $$$n$$$ 的约束。
树是无环的连通无向图。加权树的每条边都分配有权重。两个顶点之间的距离是连接它们的路径上的最小权重之和。
给你一棵带有 $$$n$$$ 个顶点的加权树,每条边的权重为 $$$1$$$。将 $$$d(v)$$$ 表示为顶点 $$$1$$$ 和顶点 $$$v$$$ 之间的距离。
如果您可以在任意两个顶点 $$$a$$$ 和 $$$b$$$ $$$(1 \le a, b \le n)$$$ 之间临时添加一条权重为 $$$x$$$ 的边,则令 $$$f(x)$$$ 为 $$$\max\limits_{1 \leq v \leq n} \ {d(v)}$$$ 的最小可能值。请注意,执行此操作后,图不再是树。
对于从 $$$1$$$ 到 $$$n$$$ 的每个整数 $$$x$$$,找到 $$$f(x)$$$。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$)。
接下来的 $$$n−1$$$ 行中的每一行都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$) 表示顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3000$$$。
输出
对于每个测试用例,在一行中打印 $$$n$$$ 个整数,对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$x$$$,其中 $$$x$$$ 等于 $$$f(x)$$$。
示例
输入 #1
3 4 1 2 2 3 1 4 2 1 2 7 1 2 1 3 3 4 3 5 3 6 5 7
输出 #1
1 2 2 2 1 1 2 2 3 3 3 3 3
注意
- 对于$$$x = 1$$$,我们可以在顶点$$$1$$$和$$$3$$$之间有一条边,然后$$$d(1) = 0$$$并且$$$d(2) = d(3) = d(4) = 1$$$,所以$$$f(1) = 1$$$。
- 对于 $$$x \ge 2$$$,无论我们添加哪条边,$$$d(1) = 0$$$、$$$d(2) = d(4) = 1$$$ 和 $$$d(3) = 2$$$,因此 $$$f(x) = 2$$$。