Building Teams

peopleCount, frendshipCount = [int(aa) for aa in input().strip().split(" ")]
frendships = sorted([sorted([int(aa)-1 for aa in input().strip().split(" ")]) for _ in range(frendshipCount)])

# print(peopleCount, frendshipCount)
# print(frendships)

friendDict = {}
for friend1, friend2 in frendships:
    if friend1 in friendDict:
        friendDict[friend1].add(friend2)
    else:
        friendDict[friend1] = set([friend2])

    if friend2 in friendDict:
        friendDict[friend2].add(friend1)
    else:
        friendDict[friend2] = set([friend1])


# print(friendDict)

team1 = set()
team2 = set()

for person in friendDict:
    inTeam1 = person in team1
    inTeam2 = person in team2
    
    if inTeam1 and inTeam2:
        print("IMPOSSIBLE")
        break
    elif inTeam1:
        team2.update(friendDict[person])
    elif inTeam2:
        team1.update(friendDict[person])
    else:
        team1.add(person)
        team2.update(friendDict[person])
# print(team1)
# print(team2)

for ii in range(peopleCount-1):
    print(1 if ii in team1 else 2,end=" ")
print(1 if ii in team1 else 2)

Test 1

Verdict: WRONG ANSWER

Test 2

Verdict: ACCEPTED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

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

Test 12

Verdict: WRONG ANSWER