Train Splitting (Codeforces 1776F)
Tags: Greedy, graphs

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

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:  

Sample Inputs:
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

Sample Outputs:
4
1 2 3 1 4 2 2 4 3
3
2 3 1

Solution (Python):
def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m) = readIntArr()
        adj = [[] for __ in range(n)]
        degrees = [0] * n
        for i in range(m):
            (u, v) = readIntArr()
            u -= 1
            v -= 1
            adj[u].append(i)
            adj[v].append(i)
            degrees[u] += 1
            degrees[v] += 1
        k = 2
        ans = [1] * m
        node_with_min_degrees = 0
        for u in range(1, n):
            if degrees[u] < degrees[node_with_min_degrees]:
                node_with_min_degrees = u
        for i in adj[node_with_min_degrees]:
            ans[i] = 2
        if n * (n - 1) // 2 == m:
            k += 1
            ans[adj[node_with_min_degrees][0]] = 3
        allans.append([k])
        allans.append(ans)
    multiLineArrayOfArraysPrint(allans)
    return
import sys
input = lambda : sys.stdin.readline().rstrip('\r\n')

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())

def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
def solve():
    (n, m) = map(int, input().strip().split())
    edges = []
    deg = [0] * (n + 1)
    for _ in range(m):
        (u, v) = map(int, input().strip().split())
        edges.append((u, v))
        deg[u] += 1
        deg[v] += 1
    c = [1] * (m + 1)
    non_full = [v for v in range(1, n + 1) if deg[v] < n - 1]
    if len(non_full) > 0:
        r = non_full[0]
        for (i, e) in enumerate(edges):
            if r in e:
                c[i + 1] = 2
    elif n == 3:
        c = [1, 1, 2, 3]
    else:
        first = True
        for (i, e) in enumerate(edges):
            if 1 in e:
                if first:
                    c[i + 1] = 2
                else:
                    c[i + 1] = 3
                first = False
    print(max(c))
    print(*c[1:])
t = int(input().strip())
for _ in range(t):
    solve()

Solution (Python):
for t in range(int(input())):
    (n, m) = map(int, input().split())
    d = {}
    for i in range(n):
        d[i + 1] = 0
    edges = []
    for i in range(m):
        (a, b) = map(int, input().split())
        edges.append([a, b])
        d[a] += 1
        d[b] += 1
    isolatedvertex = -1
    for (key, value) in d.items():
        if value != n - 1:
            isolatedvertex = key
    if isolatedvertex != -1:
        print(2)
        for edge in edges:
            if edge[0] == isolatedvertex or edge[1] == isolatedvertex:
                print(1, end=' ')
            else:
                print(2, end=' ')
    else:
        print(3)
        for edge in edges:
            if edge[0] == 1 or edge[1] == 1:
                if edge[0] == 2 or edge[1] == 2:
                    print(3, end=' ')
                else:
                    print(1, end=' ')
            else:
                print(2, end=' ')