State Definition

Define dp[u] as the maximum number of cities on any path from city $1$ to city $u$. Initialize dp[1] = 1 (you start at city $1$, so you have visited $1$ city) and dp[u] = -Infinity for all other cities. For each city $u$ in topological order, for each outgoing flight $(u, v)$, update: dp[v] = max(dp[v], dp[u] + 1) After processing all cities, check dp[n].

If it is still $-\infty$, output "IMPOSSIBLE". Otherwise, dp[n] is the answer.