Capture Game on a DAG

In this problem we consider a two‐player game played on a directed acyclic graph (DAG). At time 0, player Alin stands at node $$s_r$$ and player Alkong stands at node $$s_k$$. Both players know the full map (the DAG), and they know each other’s initial positions.

Starting from time 1, at each time step both players choose one of the following actions simultaneously: either stay at the current node or move along one of the outgoing directed edges from their current node. Once a move is started at a time step, it cannot be altered mid‐move.

The game ends immediately at a time step if, after the players’ moves, they are at the same node (i.e. Alin is caught by Alkong). Otherwise, if no capture has occurred, then after exactly L time steps (i.e. after the L-th move) it is no longer possible for either player to move further, and the game terminates at time step \(L+1\). In other words, if the game lasts for \(t_0\) time steps (i.e. a capture occurs at time step \(t_0\), or no capture within \(L\) moves so \(t_0=L\)), then Alin’s score is \(t_0\) while Alkong’s score is \(-t_0\>.

Both players are assumed to act optimally. Alin wishes to maximize the number of moves (delaying capture as long as possible), while Alkong wishes to minimize the number of moves (capturing as early as possible). It is also assumed that at every time step each player knows the current position of the other, but they do not know the move the opponent will take at the current time step.

Your task is to compute the game termination time under optimal play by both players.

Note: In this problem, all formulas must be rendered in LaTeX. For example, the starting positions are $$s_r$$ and $$s_k$$, and if the game lasts \(t_0\) moves then the scores are $$t_0$$ for Alin and $$-t_0$$ for Alkong.

inputFormat

The input begins with a line containing three integers: n (the number of nodes), m (the number of directed edges), and L (the maximum number of moves allowed if no capture occurs).

The second line contains two integers: $$s_r$$ and $$s_k$$, the starting nodes (1-indexed) of Alin and Alkong respectively.

Then follow m lines each containing two integers u and v, representing a directed edge from node u to node v. The graph is guaranteed to be acyclic.

outputFormat

Output a single integer: the termination time of the game (i.e. the number of moves played under optimal strategies). If no capture occurs within L moves, output L (the game then ends at time \(L+1\), but the number of moves played is \(L\)).

sample

3 3 3
1 3
1 2
2 3
1 3

3