CF1211H Road Repair in Treeland

在 Treeland 有 $n$ 个城市和 $n-1$ 条双向道路。每条道路连接一对不同的城市。从任意一个城市出发，只需沿着这些道路行驶，就可以到达任意其他城市。城市编号为 $1$ 到 $n$。没错，这其实描述的是一棵无向树。 政府计划修缮所有道路。每条道路都将由某个私营公司负责修缮。全国共有 $10^6$ 家私营公司，编号为 $1$ 到 $10^6$。有些公司可能不会修任何道路，有些公司可能会修多条道路。 为了简化对私营公司工作的监管，规定如下限制：对于每个城市，统计与该城市相连的所有道路的修缮公司数量，这个数量对于每个城市都不能超过 $2$。换句话说，对于每个城市，与之相连的道路最多只能由两家不同的公司修缮。 Treeland 的国家反腐委员会担心所有（或几乎所有）工作会被一家私营公司垄断。因此，委员会要求将道路分配给公司时，使得 $r$ 的值最小。对于每家公司，统计分配给它的道路数量，所有公司中分配道路最多的数量记为 $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$。

对于每个测试用例，输出两行。第一行输出一个整数 $r$，表示分配给最多道路的公司的最小可能值。第二行输出 $n-1$ 个整数 $c_1, c_2, \dots, c_{n-1}$（$1 \le c_i \le 10^6$），其中 $c_i$ 表示第 $i$ 条道路分配给的公司编号。如果有多种最优分配方案，输出任意一种即可。

由 ChatGPT 4.1 翻译