Building Teams

n,m = [int(x) for x in input().split()]
amitie = []
for i in range (n):
    amitie.append([])
ranger = [False for i in range(n)]
groupe = [False for i in range(n)]
a_tester = [0]

for i in range (m):
    a,b = [int(x)-1 for x in input().split()]
    amitie[a].append(b)
    amitie[b].append(a)

def isAmiIngroup(personne):
    groupe_liste = groupe[personne]
    for ami in amitie[personne]:
        if ranger[ami]:
            if groupe[ami] == groupe_liste:
                return True
    else:
        return False

def test_amitie():
    while a_tester:
        personne = a_tester.pop()
        ranger[personne]=True
        flag = False
        for ami in amitie[personne]:
            if ranger[ami] == False:
                a_tester.append(ami)
            else : 
                groupe[personne]= not(groupe[ami])
                if isAmiIngroup(personne):
                    return False
    return True
            
            

test_amitie()

i = 1
test = False
while i<n:
    if ranger[i] == False:
        a_tester.append(i)
        if test_amitie() == False:
            print("IMPOSSIBLE")
            test = True
            break
    i+=1
    
if not(test):
    car = ""
    for eleve in groupe:
        if eleve:
            car += "1 "
        else :
            car += "2 "
    print(car)

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: WRONG ANSWER