Checking for Cycles

The problem does not guarantee the graph is a DAG. Flight networks can have cycles like $1 \to 2 \to 3 \to 2$. If there is a cycle reachable from city $1$ that can reach city $n$, you can visit infinitely many cities by looping.

But the problem implies a unique answer exists, so either the graph is a DAG or cycles do not matter. You should check for cycles using DFS. If you find one, the problem instance is invalid or requires special handling. Most competitive programming problems guarantee valid input.