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[s]:
        if colors[u] == color:
            return False
        dfs(u, not color)
    return True


result: list[bool|None] = [None for _ in range(n)]
for s in range(n):
    result[s] = dfs(s, True)

if all(not i for i in result):
    print("IMPOSSIBLE")
else:
    print(" ".join(["1" if colors[i] else "2" for i in range(n)]))

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER