Building Teams

from collections import defaultdict

def mn():
    n, m = input().split()
    m = int(m)
    n = int(n)
    
    g = {}
    for i in range(m):
        a, b = input().split()
        a = int(a)
        b = int(b)
        g.setdefault(a, [])
        g.setdefault(b, [])
        g[a].append(b)
        g[b].append(a)

    visitedn = 0
    visited = {}
    que = list(g.keys())
    teams = [0]*(n+1)
    while visitedn < n:
        v = que.pop(0)
        visited.setdefault(v, False)
        if visited[v]:
            continue
        visited[v] = True
        for nbb in g[v]:
            visited.setdefault(nbb, False)
            if not visited[nbb]:
                que.insert(0, nbb)
            vt = teams[v]
            if vt == 0:
                vt = 1
            if teams[nbb] == vt:
                print("IMPOSSIBLE")
                return
            if vt == 1 and teams[nbb] == 0: teams[nbb] = 2
            if vt == 2 and teams[nbb] == 0: teams[nbb] = 1
        visitedn += 1

    teams.pop(0)
    print(" ".join(map(lambda x:str(x), teams)))

mn()

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED