Building Teams

if __name__ == "__main__":
    n, m = [int(x) for x in input().split(" ")]
    
    friends = {}
    for x in range(1, m + 1):
        s, e = [int(x) for x in input().split(" ")]
        if not (s in friends):
            friends[s] = []
        if not (e in friends):
            friends[e] = []
        friends[s].append(e)
        friends[e].append(s)
    
    team = [None] * (n+1)
    
    for x in range(1, n + 1):
        if team[x] != None:
            continue
        
        stack = [(x, True)]
        while len(stack) > 0:
            y, t = stack.pop()
            if team[y] != None:
                if team[y] != t:
                    print("IMPOSSIBLE")
                    exit()
                for n in friends[y]:
                    if team[n] != None and team[n] == t:
                        print("IMPOSSIBLE")
                        exit()
                continue
            team[y] = t
            if not y in friends:
                continue
            for n in friends[y]:
                stack.append((n, not t))
    
    for t in team[1:]:
        print(int(t) + 1, end=" ")

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