Building Teams

fline = list(int(x) for x in input("").split(" "))
friends = []

for i in range(fline[1]):
    friends.append(tuple(int(x) for x in input("").split(" ")))

friendlist = {}

for i in range(fline[0]):
    friendlist[i + 1] = []

for j in friends:
    friendlist[j[0]].append(j[1])
    friendlist[j[1]].append(j[0])

previous = []

has2 = False
for i in friendlist.keys():
    team1 = True
    team2 = True
    for j in previous:
        if j[1] in friendlist[i]:
            if j[0] == 1:
                team1 = False
            if j[0] == 2:
                team2 = False
    if team1:
        previous.append((1, i))
    elif team2:
        previous.append((2, i))
        has2 = True
    
    else:
        previous = "IMPOSSIBLE"
        break

if previous == "IMPOSSIBLE":
    print(previous)
else:
    if not has2:
        num = previous.pop()
        new = (2, num[1])
        previous.append(new)
    printable = ""
    for i in previous:
        
        printable += f"{i[0]} "
    print(printable.strip())

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

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: TIME LIMIT EXCEEDED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED