Building Teams

number_of_pupils, number_of_friendships = list(map(int, input().split()))

friends = []

for _ in range(number_of_friendships):
    a, b = list(map(int, input().split()))
    friends.append((a, b))

graph = {}

for i in range(1, number_of_pupils + 1):
    graph[i] = []

for friendship in friends:
    a, b = friendship
    graph[a].append(b)
    graph[b].append(a)

coloured_nodes = dict()

for node in range(1, number_of_pupils + 1):
    if node in coloured_nodes:
        continue

    queue = list()
    queue.append(node)
    coloured_nodes[node] = 1

    while len(queue) > 0:
        current_node = queue.pop()
        for adj_node in graph[current_node]:
            if not adj_node in coloured_nodes:
                coloured_nodes[adj_node] = 2 if coloured_nodes[current_node] == 1 else 1
                queue.append(adj_node)

stop = False
for node in range(1, number_of_pupils + 1):
    if stop:
        break
    node_colour = coloured_nodes[node]
    for adj_node in graph[node]:
        if coloured_nodes[adj_node] == node_colour:
                print("IMPOSSIBLE")
                stop = True
                break

if not stop:
    print_string = ""

    for item in dict(sorted(coloured_nodes.items())).items():
        print_string += f"{item[1]} "

    print(print_string.strip())

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED