Building Teams

from queue import Queue

pupils, friendships = [int(x) for x in input().split()]
adj = [[]for _ in range(pupils+1)]
teams= [1 for _ in range(pupils+1)]
distance= [0 for _ in range(pupils+1)]
visited = [False for _ in range(pupils+1)]
q = Queue()

def addAdj(adjList, pupil1, pupil2):
    adjList[pupil1].append(pupil2)
    #adjList[pupil1].append(pupil2)

def main():
    for i in range(friendships):
        pupil1, pupil2 = [int(x) for x in input().split()]
        addAdj(adj, pupil1, pupil2)

    for i in range(pupils):
        for j in range(len(distance)):
            distance[j] = 0
        for j in range(len(visited)):
            visited[j] = False
        visited[i] = True
        q.put(i)
        while not q.empty():
            s = q.get()
            for node in adj[s]:
                if visited[node]:
                    if teams[s] == teams[node]:
                        print("IMPOSSIBLE")
                        exit()
                    continue
                visited[node] = True
                distance[node] = distance[s]+1
                if teams[s] == 1:
                    teams[node] = 2
                else:
                    teams[node] = 1
                q.put(node)
    print(*teams[1:])

if __name__ == "__main__":
    main()

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: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED