CF1070I Privatization of Roads in Berland

在 Berland 有 $n$ 个城市和 $m$ 条双向道路，每条道路连接两个不同的城市。 最近，Berland 政府做出了一个艰难的决定，将道路的所有权转让给私营公司。Berland 总共有 $100500$ 家私营公司，编号为 $1$ 到 $100500$。在私有化后，每条道路必须且只能属于一家公司的所有。 反垄断委员会要求，私有化后每家公司最多只能拥有两条道路。Berland 的城市规划师也提出了意见：每个城市相邻的道路，最多只能由 $k$ 家不同的公司拥有。 请帮助政府分配道路的所有权，使得上述两个条件都被满足。也就是说，每家公司最多拥有两条道路，并且每个城市相邻的道路最多属于 $k$ 家不同的公司。

输入包含一个或多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 300$），表示测试用例的数量。请分别解决每个测试用例，测试用例之间完全独立，互不影响。 接下来的若干行描述各个测试用例。每个测试用例的第一行包含三个用空格分隔的整数 $n$、$m$ 和 $k$（$2 \le n \le 600$，$1 \le m \le 600$，$1 \le k \le n-1$），分别表示城市数量、道路数量和每个城市相邻道路最多属于的公司数。 接下来的 $m$ 行，每行包含两个用空格分隔的整数 $a_i$、$b_i$（$1 \le a_i, b_i \le n$，$a_i \ne b_i$），表示第 $i$ 条道路连接城市 $a_i$ 和 $b_i$。所有道路都是双向的。任意一对城市之间最多只有一条道路。 所有测试用例中 $n$ 的总和不超过 $600$，$m$ 的总和不超过 $600$。

输出 $t$ 行，第 $i$ 行为第 $i$ 个测试用例的答案。对于每个测试用例，输出 $c_1, c_2, \dots, c_m$，用空格分隔，其中 $c_i$（$1 \le c_i \le 100500$）表示你分配给第 $i$ 条道路的公司编号。如果有多种方案，可以输出任意一种。如果无解，则输出 $c_1 = c_2 = \ldots = c_m = 0$。

由 ChatGPT 4.1 翻译