Building Teams

from collections import deque

n, m = [int(x) for x in input().split()]

classroom = [[] for i in range(n + 1)]
for i in range(m):
    a, b = [int(x) for x in input().split()]
    classroom[a].append(b)
    classroom[b].append(a)

team = [0] * (n + 1)

def bfs(start):
    queue = deque([start])
    team[start] = 1
    while queue:
        u = queue.popleft()
        for i in classroom[u]:
            if team[i] == 0:
                team[i] = 3 - team[u]
                queue.append(i)
            elif team[i] == team[u]:
                return False
    return True

impossible = False
for i in range(1, n + 1):
    if team[i] == 0:
        if not bfs(i):
            impossible = True
            break

if not impossible:
    del team[0]
    print(*team)
else:
    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