Building Teams

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    pupils = int(input_data[0])
    frienships = int(input_data[1])

    adj_list = [[] for _ in range(pupils+1)]
    groups = [0 for _ in range(pupils+1)]
    stack = []

    idx = 2
    for _ in range(frienships):
        pupil1 = int(input_data[idx])
        pupil2 = int(input_data[idx+1])
        adj_list[pupil1].append(pupil2)
        adj_list[pupil2].append(pupil1) 
        idx += 2

    for pupil in range(1, pupils+1):
        if groups[pupil] == 0:
            stack.append(pupil)
            groups[pupil] = 1 

            while stack:
                aux = stack.pop()
                for x in adj_list[aux]:
                    if groups[x] == 0:
                        stack.append(x)
                        groups[x] = 3 - groups[aux]
                    elif groups[x] == groups[aux]:
                        print("IMPOSSIBLE")
                        return

    print(*(groups[1:]))

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