Building Teams

from collections import deque


def main():
    n, m = map(int, input().split())

    friendships = []

    for _ in range(m):
        a, b = map(int, input().split())
        friendships.append((a, b))


    adjacency_list = {}

    for i in range(1, n+1):
        adjacency_list[i] = []

    for a, b in friendships:
        adjacency_list[a].append(b)
        adjacency_list[b].append(a)


    teams = [0] * (n + 1)

    for start in range(1, n+1):
        if teams[start] != 0:
            continue

        teams[start] = 1

        queue = deque([start])
        

        while queue:
            node = queue.popleft()

            for neighbors in adjacency_list[node]:
                if teams[neighbors] == 0:
                    teams[neighbors] = 3 - teams[node]
                    queue.append(neighbors)

                elif teams[neighbors] == teams[node]:
                    print("IMPOSSIBLE")
                    return


    for i in range(len(teams)):
        if i == 0:
            continue

        print(teams[i])





if __name__ == "__main__":
    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