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):
    node_colour = 1
    if node in coloured_nodes:
        continue

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

    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)


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

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: WRONG ANSWER

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: TIME LIMIT EXCEEDED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER