Treeland 有 $$$n$$$ 个城市和 $$$n-1$$$ 双向道路。每条道路连接一对不同的城市。您可以从任何城市开车前往任何其他城市,只需沿着道路行驶即可。城市编号从 $$$1$$$ 到 $$$n$$$。是的,当然,您在这个描述中认出了一棵无向树。
政府计划修复所有道路。每条道路都将由一些私人公司修复。该国总共有 $$$10^6$$$ 私营公司,编号从 $$$1$$$ 到 $$$10^6$$$。可能有些公司根本不会修路,有些公司会修很多条路。
为了简化对私营公司工作的控制,引入了以下限制:对于每个城市,我们计算一端有该城市的不同修路公司的数量。每个城市的这个数字不应超过 $$$2$$$。也就是说,对于每个城市来说,修缮与该城市相关的道路的不同公司不应超过两家。
Treeland 国家反腐败委员会担心所有(或几乎所有)工作都将交给一家私营公司。因此,委员会要求在公司之间分配道路,以尽量减少 $$$r$$$ 的价值。对于每个公司,我们计算分配给它的道路数量,所有公司中最大的道路数量称为$$$r$$$。
帮助政府找到一种方法,按照要求的方式在公司之间分配所有道路。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 输入中输入案例的数量。接下来,给出输入案例本身。每个测试用例集的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3000$$$) — Treeland 中的城市数量。接下来,在$$$n-1$$$行中写入道路:一行包含两个整数$$$x_i$$$、$$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$),表示第$$$i$$$条道路连接城市$$$x_i$$$和$$$y_i$$$。
保证输入中所有测试用例的所有值$$$n$$$之和不超过$$$3000$$$。
输出
打印输入中所有 $$$t$$$ 测试用例的答案。每个测试用例必须以包含 $$$r$$$ 的行开始——分配给最常用公司的最小可能道路数。接下来,在下一行中打印 $$$n-1$$$ 数字 $$$c_1, c_2, \dots, c_{n-1}$$$ ($$$1 \le c_i \le 10^6$$$),其中 $$$c_i$$$ 表示修复第 $$$i$$$ 条道路的公司。如果有多个最佳分配,请打印其中任何一个。
示例
输入 #1
3 3 1 2 2 3 6 1 2 1 3 1 4 1 5 1 6 7 3 1 1 4 4 6 5 1 2 4 1 7
输出 #1
1 10 20 3 1 1 1 2 2 2 11 11 12 13 12 13