Building Teams

import sys

sys.setrecursionlimit(10 ** 6)

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
visited = [False for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)

colors: list[bool | None] = [None for _ in range(n)]


def dfs(i, color):
    if visited[i]:
        return True

    visited[i] = True
    colors[i] = color

    for u in adj[i]:
        if colors[u] == color:
            return False
        if not dfs(u, not color):
            return False
    return True


for s in range(n):
    if not dfs(s, True):
        break
else:
    print(" ".join(["1" if colors[i] else "2" for i in range(n)]))
    exit()
print("IMPOSSIBLE")

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED