Train Splitting
Contest: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1700
Tags: constructive algorithms, graphs, greedy

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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:

Example input:
2
5 9
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
3 3
1 2
3 1
2 3

Example output:
4
1 2 3 1 4 2 2 4 3
3
2 3 1

Editorial:
The problem is equivalent to:
Formal statement: Given a connected graph, paint its edges with several colors so that the edges of any single color do not make the graph connected, but any $$$2$$$ colors together make the graph connected.
This is a constructive problem and there can be a lot of different approaches. We left the limitations small on purpose, so that you could let your imagination run wild. We will describe a simple solution which works in time proportional to the size of the input.
How can we make sure the graph is not connected? Take a vertex and remove all incident edges. So if we paint edges incident to one vertex with color $$$1$$$ and all other edges with color $$$2$$$, then color $$$2$$$ will not connect the graph, while colors $$$1$$$ and $$$2$$$ together will connect. And what about color $$$1$$$ alone? It will connect the graph if and only if the chosen vertex was connected to all of the other vertices, so if we can find a vertex that is not connected to all of the other vertices, we are done.
Unless the graph is complete, i.e., it contains all possible edges, we can find such a vertex. If, on the other hand, the graph is complete, we can paint the edges from one vertex with two different colors (at least one of such edges with one color and at least one of such edges with the other), and all the other edges with the third color. You can verify that all the conditions are satisfied by this coloring.
The complexity of this solution is $$$O(n+m)$$$.