CF1776F.Train Splitting

There are $n$ big cities in Italy, and there are $m$ train routes between pairs of cities. Each route connects two different cities bidirectionally. Moreover, using the trains one can reach every city starting from any other city.

Right now, all the routes are operated by the government-owned Italian Carriage Passenger Company, but the government wants to privatize the routes. The government does not want to give too much power to a single company, but it also does not want to make people buy a lot of different subscriptions. Also, it would like to give a fair chance to all companies. In order to formalize all these wishes, the following model was proposed.

There will be $k \ge 2$ private companies indexed by $1, \, 2, \, \dots, \, k$. Each train route will be operated by exactly one of the $k$ companies. Then:

• For any company, there should exist two cities such that it is impossible to reach one from the other using only routes operated by that company.
• On the other hand, for any two companies, it should be possible to reach every city from any other city using only routes operated by these two companies.

Find a plan satisfying all these criteria. It can be shown that a viable plan always exists. Please note that you can choose the number $k$ and you do not have to minimize or maximize it.

意大利有 $n$ 座大城市，城市之间共有 $m$ 条铁路线路，每条线路双向连接两个不同的城市。此外，仅通过这些铁路线路，可以从任意一座城市出发到达其余所有城市（即整个铁路网络是连通的）。

目前，所有线路均由国有公司“意大利客运车厢公司”运营；但政府计划将这些线路私有化。政府既不希望将过多权力赋予某一家公司，也不希望民众被迫购买大量不同的订阅服务；同时，政府还希望为所有公司提供公平的竞争机会。为形式化上述所有目标，提出了如下模型：

将有 $k \ge 2$ 家私营公司，编号为 $1,\, 2,\, \dots,\, k$。每条铁路线路将恰好由这 $k$ 家公司中的一家运营。要求满足：

• 对于任意一家公司，都存在两座城市，使得仅使用该公司运营的线路无法从其中一座城市到达另一座城市；
• 反之，对于任意两家公司，仅使用这两家公司运营的线路，必须能够从任意一座城市出发到达其余所有城市（即这两家公司运营的线路所构成的子图是连通的）。

请给出一个满足上述所有条件的分配方案。可以证明，这样的可行方案总是存在的。注意：你可以自由选择 $k$ 的值，无需最小化或最大化它。

Each test contains multiple test cases. The first line contains an integer $t$ ($1 \le t \le 1000$) — the number of test cases. The descriptions of the $t$ test cases follow.

The first line of each test case contains two integers $n$ and $m$ ($3 \le n \le 50$, $n-1 \le m \le n(n-1)/2$) — the number of cities and the number of train routes.

The next $m$ lines contain two integers $u_i$ and $v_i$ each ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) — the $i$-th train route connects cities $u_i$ and $v_i$.

It is guaranteed that the routes connect $m$ distinct pairs of cities. It is guaranteed that using the trains one can reach every city starting from any other city.

The sum of the values of $n$ over all test cases does not exceed $5000$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

保证这 $m$ 条线路连接的是 $m$ 个互不相同的无序城市对。保证通过火车可以从任意一座城市出发到达其他所有城市。

所有测试用例中 $n$ 的值之和不超过 $5000$。

For each test case, on the first line print an integer $k$ ($2 \le k \le m$) — the number of companies in your plan; on the second line print $m$ integers $c_1, \, c_2, \, \dots, \, c_m$ ($1 \le c_i \le k$) — in your plan company $c_i$ operates the $i$-th route.

If there are multiple valid plans, you may print any of them.

对于每个测试用例，第一行输出一个整数 $k$（$2 \le k \le m$）—— 表示你所制定方案中公司的数量；第二行输出 $m$ 个整数 $c_1, \, c_2, \, \dots, \, c_m$（$1 \le c_i \le k$）—— 在你的方案中，第 $i$ 条线路由公司 $c_i$ 运营。

若存在多个合法方案，你可以输出其中任意一个。

In the first test case, the output is illustrated in the following picture, where different colors correspond to different companies (blue for $1$, red for $2$, green for $3$, and yellow for $4$):

If we consider, for example, only companies $2$ and $3$, we can see that from any city it is possible to reach every other city (picture on the left below). However, if we restrict to company $2$ alone, it becomes impossible to reach city $5$ from city $1$ (picture on the right).

In the second test case, the output is illustrated in the following picture:

在第一个测试用例中，输出如下图所示，其中不同颜色对应不同的公司（蓝色代表公司 $1$，红色代表公司 $2$，绿色代表公司 $3$，黄色代表公司 $4$）：

例如，若仅考虑公司 $2$ 和 $3$，我们可以看到从任意城市出发均能到达其余所有城市（如下图左侧所示）。然而，若仅限制使用公司 $2$ 的路线，则无法从城市 $1$ 到达城市 $5$（如下图右侧所示）。

在第二个测试用例中，输出如下图所示：