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()
visited = set()

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

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

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

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

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