Problem Background

(五) Dialogue of Hearts

The old capital is still snowing.

After an unknown distance, I have left the bustling streets behind.

A massive palace looms faintly in the distance.

Is that the Palace of Earth Spirits?

My heart suddenly tightens.

This is where the most terrifying mind-reading demon of the old hell resides.

Kokoro, the ancient demon, has the ability to read minds. Humans, monsters, even vengeful spirits, stand before her as if naked, with no secrets left. Moreover, it is said that in battles, she uses hypnosis to continuously stir up terrifying memories deep within her opponents, crushing them psychologically. Such a demon is naturally disliked.

However, this underground journey cannot end just because we are about to encounter a terrifying demon.

Knock knock knock, I knock on the door of the Palace of Earth Spirits.

"A visitor? That's rare."

Before me stands a girl, dressed in blue with a pink skirt, and pink hair.

A large red eye hangs from her chest, connected to her body by six tubes around the eye.

She looks very gentle, not at all as terrifying as rumored.

"A human from the outside world traveling underground? That's very rare, to have found this place."

"Looks like you have no other intentions, just want to have a look around, then come in."

I enter the door.

Indeed, the Palace of Earth Spirits is a grand palace with peach-pink and black floors, and patterned windows.

Before me is a wide set of stairs leading to the second floor, then branching into two passages on the left and right.

"Beautiful, isn't it? The spacious space is loved by the pets."

Thus, I follow Kokoro into her working room, and we sit on the sofa chatting for a long time, though I rarely speak.

During the conversation, I learn that she has a younger sister, Kogasa, who closed her third eye because she didn't want others to dislike her for being able to read minds. Kokoro often plays with her pets to console her sister.

The Palace of Earth Spirits, Kokoro and her sister, the pets, have been living a peaceful and warm life.

"Since you're here, join us in our game." Kokoro invites us to participate in their game.

What kind of game do underground demons play?

And so, I agree to join Kokoro and Kogasa in their "Hide and Seek Beyond Consciousness."

Though called "Hide and Seek," it is quite different from the ordinary version, more akin to a "Catching Game."

Kokoro and Kogasa start at two different locations, and Kokoro wins if she catches Kogasa.

But why is it called "Hide and Seek"?

Kogasa can act unconsciously, making those around her subconsciously ignore her presence, similar to invisibility, but not exactly. It's an interesting ability, perhaps due to closing her third eye?

We had a lot of fun. Sometimes, accidentally touching Kogasa's hand unconsciously startled me.

After a while, the sisters got tired, and Kokoro had work to attend to, so she left first.

The pets seemed unsatisfied and wanted to continue.

"But in this old hell, besides the master's sister Kogasa, where else can we find a demon who can manipulate unconsciousness?

Forget it, let's just play a regular catching game." Rin suggested.

So the pets quickly immersed themselves in "Hide and Seek Beyond Consciousness."

At some point, I felt a chill at my back, and turning around, it was Kogasa.

We stood there watching the pets play.

Though I don't know why I could be so patient to watch for so long, hours passed, and we still stood there.

Kogasa seemed to have some questions, and after a brief exchange, I summarized her doubts.

(See Problem Description)

This problem is indeed unsolvable for the unconscious Kogasa.

It's truly grateful to have talked so happily with the sisters, so I'll do my best to think about this problem.

(Subsequent plot see solution, next see T4)

Problem Description

Problem Summary:

On a directed acyclic graph, Rin and Kagerou stand at nodes numbered $s_r$ and $s_k$ respectively at time 0. Both know each other's initial positions and have complete knowledge of the map.

Starting from time 1, each moment Rin and Kagerou can choose to stay still or move to an adjacent node. Their movements start simultaneously each moment and cannot change direction mid-movement.

The game ends immediately when Kagerou catches Rin. If Kagerou never catches Rin, they cannot move anymore after time $t$, and the game ends at time $t+1$.

Kagerou's goal is to catch Rin as quickly as possible (catching is defined as standing on the same node at the same time), while Rin's goal is to avoid being caught for as long as possible. Specifically, if a game lasts $t_0$ moments, Rin's score is $t_0$, and Kagerou's score is $-t_0$. Both aim to maximize their own score (or expected score).

We assume that Rin and Kagerou always know each other's position during the game. They cannot predict where the other will move at the next moment.

Kogasa wants to know the expected value of the game's end time under optimal decisions by both parties.

Input and Output Formats

Input Format

The first line contains five integers $n$, $m$, $s_r$, $s_k$, $t$, separated by spaces.

$n$ represents the number of nodes on the map, and $m$ represents the number of edges.

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

Output Format

A real number, rounded to three decimal places, representing the expected value of the game's end time.

Your answer must be exactly the same as the standard answer to be considered correct.

Sample Input and Output

Sample Input #1

3 2 1 2 10
1 3
2 3

Sample Output #1

11.000

Sample Input #2

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

Sample Output #2

2.333

Notes

Sample Explanation:

Sample 1: Rin can simply stay still, and Kagerou cannot catch Rin within the first $t$ units of time, so the answer is $t+1$, which is 11.000.

Sample 2: No comment.

Data Range:

For 30% of the data, $n \leqslant 3$, bundled testing.

For 100% of the data, $n, t \leqslant 20$, with the first 40% and the last 30% of the data bundled separately.

Hint:

This problem mainly tests whether you can use the correct method to calculate the answer, with no strict time limit for the algorithm's execution.

by orangebird

见题面 Input 部分

见题面 Output 部分