Building Teams

from collections import deque

buffer = input().split()
n = int(buffer[0])
m = int(buffer[1])

color = [0] * n
graph = [[] for _ in range(n)]

for _ in range(m):
    buffer = input().split()
    a = int(buffer[0]) - 1
    b = int(buffer[1]) - 1
    graph[a].append(b)
    graph[b].append(a)

def color_everyone(start):
    queue = deque([start])
    color[start] = 1
    while queue:
        node = queue.popleft()
        for j in graph[node]:
            if color[j] == 0:
                color[j] = 3 - color[node]
                queue.append(j)
            elif color[j] == color[node]:
                print("IMPOSSIBLE")
                exit(0)

for i in range(n):
    if color[i] == 0:
        color_everyone(i)

for c in color:
    assert 1<=c<=2

print(" ".join(map(str, color)))

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