Here's the solution:
function longestRoute(n, edges):
adj := array of lists, size n + 1
indegree := array of size n + 1, initialized to 0
dist := array of size n + 1, initialized to -infinity
parent := array of size n + 1, initialized to -1
queue := empty queue
topoOrder := empty list
for each edge (a, b) in edges:
add b to adj[a]
indegree[b] := indegree[b] + 1
for i from 1 to n:
if indegree[i] = 0 then
push i to queue
while queue is not empty:
u := pop from queue
add u to topoOrder
for each v in adj[u]:
indegree[v] := indegree[v] - 1
if indegree[v] = 0 then
push v to queue
dist[1] := 0
for each u in topoOrder:
if dist[u] ≠ -infinity then
for each v in adj[u]:
if dist[u] + 1 > dist[v] then
dist[v] := dist[u] + 1
parent[v] := u
if dist[n] = -infinity then
print "IMPOSSIBLE"
else
path := reconstruct path from 1 to n using parent array
print length of path
print path
Time: . Space: .