Longest Flight Route - Algorithm

$1.$ Run Kahn's algorithm to get the topological order of the cities.

If the graph has a cycle, topological sort fails, which means there's no valid route (you'd loop forever).

$2.$ Initialize dist[1] = 0 (city $1$ is the start, $0$ edges to reach it). Set all other dist[i] = -Infinity (not reachable yet).

$3.$ Process cities in topological order.

For each city $u$ with dist[u] != -Infinity: For each neighbor $v$ where edge $u \to v$ exists: If dist[u] + 1 > dist[v]: Update dist[v] = dist[u] + 1 and set parent[v] = u.

$4.$ After processing all cities, check dist[n].

If dist[n] = -Infinity, print IMPOSSIBLE. Otherwise, reconstruct the path using the parent array.

This runs in $O(V + E)$ time and uses $O(V)$ space.