Building Teams

import sys

sys.setrecursionlimit(100000)


def task1(n, relations, team):
    for i in range(1, n + 1):
        if team[i] == 0:
            if not dfs(i, relations, team):
                print("IMPOSSIBLE")
                return
    team = team[1:]
    print(" ".join(map(str, team)))


def dfs(i, relations, team):
    if team[i] == 0:
        team[i] = 1
    if team[i] == 1:
        friend_team = 2
    else:
        friend_team = 1
    for friend in relations[i]:
        if team[friend] == 0:
            team[friend] = friend_team
            if not dfs(friend, relations, team):
                return False
        elif team[friend] != friend_team:
            return False
    return True


if __name__ == "__main__":
    n, m = map(int, input().split())
    relations = [[] for _ in range(n + 1)]
    team = [0] * (n + 1)

    for i in range(m):
        u, v = map(int, input().split())
        relations[u].append(v)
        relations[v].append(u)
    task1(n, relations, team)

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