Building Teams

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

def checkOnePerson(person, team1, team2, friendDict, checked):
    # print("Bef", person)
    if checked[person] != 0:
        return
    # print("Aft", person)
    checked[person] = 1
    inTeam1 = person in team1
    inTeam2 = person in team2

    # if person == 3 or person == 4:
    #     # print(inTeam1, inTeam2)
    #     print(friendDict[person])
    #     print(4 in team1, 4 in team2)

    if inTeam1 and inTeam2:
        print("IMPOSSIBLE")
        exit()
    elif inTeam1:
        if person in friendDict:
            team2.update(friendDict[person])
            for friend in friendDict[person]:
                checkOnePerson(friend, team1, team2, friendDict, checked)
    elif inTeam2:
        if person in friendDict:
            team1.update(friendDict[person])
            for friend in friendDict[person]:
                checkOnePerson(friend, team1, team2, friendDict, checked)
    else:
        team1.add(person)
        checked[person] = 0
        checkOnePerson(person, team1, team2, friendDict, checked)


friendDict = {}
# print(frendships)
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])


team1 = set()
team2 = set()
# print(friendDict)
# for person in range(peopleCount):
#     inTeam1 = person in team1
#     inTeam2 = person in team2
    
#     if inTeam1 and inTeam2:
#         print("IMPOSSIBLE")
#         exit()
#     elif inTeam1:
#         if person in friendDict:
#             team2.update(friendDict[person])
#     elif inTeam2:
#         if person in friendDict:
#             team1.update(friendDict[person])
#     else:
#         team1.add(person)
#         if person in friendDict:
#             team2.update(friendDict[person])
for person in range(peopleCount):
    # print(person)
    checkOnePerson(person, team1, team2, friendDict, checked)
# print(friendDict)
# print(team1)
# print(team2)
# exit()
# print(team1.intersection(team2))
if len(team1.intersection(team2)) != 0:
    print("IMPOSSIBLE")
    exit()
for person in range(peopleCount-1):
    if person in team1:
        print(1, end=" ")
    else:
        print(2, end=" ")
if peopleCount-1 in team1:
    print(1)
else:
    print(2)

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

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED