Building Teams

# Online Python compiler (interpreter) to run Python online.
# Write Python 3 code in this online editor and run it.
import sys

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

    n = int(input_data[0])
    m = int(input_data[1])

    adj_list = [[] for _ in range(n + 1)]
    idx = 2
    for _ in range(m):
        u = int(input_data[idx])
        v = int(input_data[idx + 1])
        adj_list[u].append(v)
        adj_list[v].append(u)
        idx += 2

    teams = [0] * (n + 1)
    stack = []
    current_team = 1

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

            while stack:
                curr = stack.pop()
                
                if teams[curr] == 0:
                    teams[curr] = current_team
                    current_team = 2 if current_team == 1 else 1

                for neighbor in adj_list[curr]:
                    if teams[neighbor] == 0:
                        stack.append(neighbor)
                    elif teams[neighbor] == teams[curr]:
                        print("IMPOSSIBLE")
                        return

    print(*(teams[1:]))

main()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED