← 返回题目列表

Codeforces · 1211/H

H. 林地道路维修

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

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