Let \({\rm dp}[v][0]\) and \({\rm dp}[v][1]\) be the answer when the piece is initially on Vertex \(v\), and Takahashi and Aoki play first, respectively. (DP stands for Dynamic Programming)

In case of DAG (Directed Acyclic Graph)

If the outdegree of \(v\) is \(0\), then \({\rm dp}[v][0]={\rm dp}[v][1]=0\). Otherwise, we have
\({\rm dp}[v][0]=\min {\rm dp}[u][1]\),
\({\rm dp}[v][1]=\max {\rm dp}[u][0]\)
(where \(u\) spans over all vertices directly reachable from \(v\)).

Backward induction

If the graph is not a DAG, we cannot directly apply the algorithm above because there is a loop in the definition of the DP table.
Instead, consider filling the DP table by starting from the terminal states and traversing backward the process of the game. Such a method of analysis is generally called backward induction.

For example, consider the following question: is the answer for the original problem infinity? We can solve it by filling a boolean-valued DP table \({\rm finite}[v][i]\) as follows.

If the outdegree of \(v\) is \(0\), then \({\rm finite}[v][0]={\rm finite}[v][1]={\rm True}\). Initialize the other elements with \({\rm False}\) and update them as follows:

• For a vertex \(v\), if there is at least one vertex \(u\) directly reachable from \(v\) such that \({\rm finite}[u][1]={\rm True}\), then let \({\rm finite}[v][0]\) be \({\rm True}\).
• For a vertex \(v\), if all vertex \(u\) directly reachable from \(v\) satisfy \({\rm finite}[u][0]={\rm True}\), then let \({\rm finite}[v][1]\) be \({\rm True}\).

When there is nothing to update, \({\rm finite}\) table reaches the answer. With a proper implementation, this algorithm works in a total of \(O(M)\) time.

Calculation of the DP

The original problem can be solved in almost the same way. However, when we tried finding \({\rm finite}[v][0]\), it was sufficient to have at least one \({\rm True}\) in the reachable vertices, while in the original problem, we need to minimize the answer. We can achieve this by prioritizing the transition on vertices with smaller confirmed answer. The time complexity is \(O(M\log N)\).

More basic similar problem: ABC209E Shiritori