Longest route

import heapq

n, m = [int(x) for x in input().split()]

matrice = {i:[] for i in range(n)}
matrice_retour = {i:[] for i in range(n)}
for _ in range(m):
    a, b = [int(x) for x in input().split()]
    matrice[a-1].append((b-1,-1))
    matrice_retour[b-1].append(a-1)

distance = [float('inf') for _ in range(n)]
distance[0] = 0
visited = set()
priority_queue = []
heapq.heappush(priority_queue, (0, 0))

while len(priority_queue) > 0:
    actual_node = heapq.heappop(priority_queue)[1]
    if actual_node in visited:
        continue
    visited.add(actual_node)
    for next_node, dist in matrice[actual_node]:
        prev_val = distance[next_node]
        distance[next_node] = min(distance[next_node], distance[actual_node] + dist)
        if distance[next_node] != prev_val:
            heapq.heappush(priority_queue, (distance[next_node], next_node))

if distance[-1] < float('inf'):
    tab = []
    node = n-1
    while node != 0:
        tab.append(node)
        for next_node in matrice_retour[node]:
            if distance[node] == (distance[next_node] - 1):
                node = next_node
                break
    tab.append(0)
    print(len(tab))
    while len(tab) > 0:
        elt = tab.pop()
        print(elt+1, end=' ')
else:
    print("IMPOSSIBLE")

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED