Building Teams

#!/usr/bin/env python3

'''Building teams'''

import sys

N,M = [int(x) for x in input().split()]
GRAPH = [[] for _ in range(N + 1)]
NOT_VISITED = set(range(2, N + 1))
SOLUTION = [0 for _ in range(N+1)]

def dfs(node):
    '''Depth-first search'''
    nodes_to_visit = [node]
    while len(nodes_to_visit) > 0:
        node = nodes_to_visit[-1]
        if SOLUTION[node] == 0:
            SOLUTION[node] = 1
        node_number = SOLUTION[node]
        if len(GRAPH[node]):
            next_node = GRAPH[node].pop()
            if (SOLUTION[next_node] != 0) and (SOLUTION[next_node] == SOLUTION[node]):
                print('IMPOSSIBLE')
                sys.exit()
            if next_node in NOT_VISITED:
                NOT_VISITED.remove(next_node)
                SOLUTION[next_node] = node_number%2 + 1
                nodes_to_visit.append(next_node)
        else:
            nodes_to_visit.pop()

def main():
    '''Main'''
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        GRAPH[a].append(b)
        GRAPH[b].append(a)

    dfs(1)
    while len(NOT_VISITED) > 0:
        node = NOT_VISITED.pop()
        dfs(node)

    for elt in SOLUTION[1:]:
        print(str(elt), end=' ')

main()

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