CF1776F Train Splitting

意大利有 $n$ 个大城市，城市之间有 $m$ 条火车线路。每条线路连接两个不同的城市，且是双向的。此外，利用这些火车线路，从任意一个城市出发都可以到达其他所有城市。 目前，所有线路都由国有的意大利客运公司运营，但政府希望将这些线路私有化。政府既不希望某家公司拥有过多权力，也不希望人们需要购买太多不同公司的订阅，同时还希望给所有公司公平的机会。为此，提出了如下模型： 将有 $k \ge 2$ 家私营公司，编号为 $1,\,2,\,\dots,\,k$。每条火车线路将由 $k$ 家公司中的一家独立运营。要求： - 对于任意一家公司，存在两个城市，使得仅使用该公司运营的线路无法从一个城市到达另一个城市。 - 另一方面，对于任意两家公司，使用这两家公司运营的线路，任意两个城市之间都可以互相到达。 请给出一种满足上述所有条件的分配方案。可以证明，总是存在可行方案。注意，你可以自行选择 $k$ 的值，并且不需要最小化或最大化 $k$。

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试数据组数。接下来是 $t$ 组测试数据。 每组测试数据的第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 50$，$n-1 \le m \le n(n-1)/2$），分别表示城市数和火车线路数。 接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示第 $i$ 条火车线路连接城市 $u_i$ 和 $v_i$。 保证每条线路连接的是不同的城市对，且所有线路连通整个城市集合，即任意两个城市之间都可以通过火车线路互达。 所有测试数据中 $n$ 的总和不超过 $5000$。

对于每组测试数据，第一行输出一个整数 $k$（$2 \le k \le m$），表示你方案中的公司数；第二行输出 $m$ 个整数 $c_1,\,c_2,\,\dots,\,c_m$（$1 \le c_i \le k$），表示在你的方案中，第 $i$ 条线路由公司 $c_i$ 运营。 如果有多种可行方案，你可以输出任意一种。

在第一个测试点中，输出结果如下图所示，不同颜色代表不同公司（蓝色为 $1$，红色为 $2$，绿色为 $3$，黄色为 $4$）：  例如，仅考虑公司 $2$ 和 $3$ 时，可以发现任意两个城市之间都可以互达（下图左）。但如果只考虑公司 $2$，则无法从城市 $1$ 到达城市 $5$（下图右）。  第二个测试点的输出结果如下图所示：  由 ChatGPT 4.1 翻译