Description

Problem summary.

On a directed acyclic graph, A Rin and A Kong stand at time $0$ on nodes numbered $s_r$ and $s_k$, respectively. Both know each other’s initial positions and have full knowledge of the map.

Starting from time $1$, at each time step both A Rin and A Kong may either stay put or move to an adjacent node along a directed edge. Their moves at each time step start simultaneously, and they cannot change direction mid-step.

When A Rin is caught by A Kong, the game ends immediately. If A Kong never catches A Rin, then after time $t$ ends, neither can move anymore, and the game ends at time $t+1$.

A Kong’s goal is to catch A Rin as quickly as possible (catching means being on the same node at the same time), while A Rin’s goal is to avoid being caught for as long as possible. Specifically, if a game lasts for $t_0$ time steps, A Rin’s score is $t_0$, and A Kong’s score is $-t_0$. Both aim to maximize their own (expected) scores.

We assume that throughout the process A Rin and A Kong always know each other’s current positions. At time $t$, neither can tell where the other will choose to move at time $t+1$.

Koishi wants to know: under optimal play by both sides, what is the expected ending time of the game?

Input Format

The first line contains $5$ integers $n$, $m$, $s_r$, $s_k$, $t$, separated by spaces. Here, $n$ is the number of nodes and $m$ is the number of edges.

The next $m$ lines each contain two integers $a$, $b$, indicating a directed edge from $a$ to $b$ (no multiple edges).

Output Format

Output a real number, rounded to $3$ decimal places, which is the expected ending time of the game.

Your answer must exactly match the standard answer to be accepted.

3 2 1 2 10
1 3
2 3

11.000

6 8 2 1 2
1 2
1 3
1 5
2 3
3 5
5 6
6 4
2 4

2.333

Hint

Sample explanation.

Sample $1$: If A Rin always stays still, then A Kong cannot catch A Rin within the first $t$ units of time; the answer is $t+1$, i.e.,

11.000

Constraints.

This problem uses bundled testdata.

• For $30\%$ of the data, $n \leqslant 3$.
• For the remaining $70\%$ of the data, $n, t \leqslant 20$. Among these, the first $40\%$ and the last $30\%$ are bundled and tested separately.

Tip: This problem mainly checks whether you can use the correct method to compute the answer; strict time limits on the algorithm are not the focus.

by orangebird.

Translated by ChatGPT 5