Building Teams

inp = input().split(" ")

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

connections = [[] for _ in range(n)]

for i in range(m):
    friendship = input().split(" ")
    a = int(friendship[0])
    b = int(friendship[1])

    connections[a - 1].append(b - 1)
    connections[b - 1].append(a - 1)

groups = [-1 for _ in range(n)]

for i in range(n):
    # Perform BFS on this graph

    if groups[i] != -1:
        continue

    q = [i]
    groups[i] = 0
    group = 1
    while len(q) > 0:
        s = q.pop(0)

        for neighbor in connections[s]:
            if groups[neighbor] != -1:
                expected_group = (groups[s] + 1) % 2
                if groups[neighbor] != expected_group:
                    print("IMPOSSIBLE")
                    quit()
                continue
            groups[neighbor] = (groups[s] + 1) % 2
            q.append(neighbor)

print(" ".join([str(i) for i in groups]))

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

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