Description

问题摘要

在一个有向无环图上，阿燐和阿空第0个时刻分别站在编号为 $s_r$，$s_k$ 的节点，二人都知道双方的初始位置，对地图完全了解。

从第 $1$ 个时刻起，每个时刻阿燐和阿空都可以选择站着不动，也可以选择移动到相邻的节点，二人每时刻的移动是同时开始的，并且不能中途改变方向。

阿燐被阿空捉住时，游戏立即结束。如果阿空一直没有捉住阿燐，第 $t$ 个时刻结束后两人就不能再继续移动了，游戏将在第 $t+1$ 个时刻结束。

阿空的目的是尽快捉住阿燐(捉住的定义是与阿燐同一时刻站在同一节点)，而阿燐的目的是尽可能更长时间不被阿空捉住。具体而言，若一场游戏进行了 $t_0$ 时刻，阿燐的得分是 $t_0$ ，阿空的得分是 $-t_0$，双方都希望自己得分(或得分的期望值)更高。

我们认为在这个过程中阿燐和阿空随时都能知道对方的位置。两人在第 $t$ 个时刻不能看出第 $t+1$ 个时刻对方要走到哪里。

恋恋想知道，在双方最优决策的情况下，游戏结束时刻的期望值是多少。

Input Format

第一行 $5$ 个整数 $n$，$m$，$s_r$，$s_k$，$t$，用空格隔开，下同。$n$ 表示地图点数，$m$ 表示边数。

接下来 $m$ 行，每行两个整数 $a$，$b$，表示从 $a$ 到 $b$ 有一条单向边（不存在重边）。

Output Format

一个实数，四舍五入保留 $3$ 位小数，表示游戏结束时刻的期望值。

你的答案必须和标准答案完全相同才算正确。

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

样例解释

样例 $1$：阿燐只要一直不动，阿空在前$t$单位时间内就无法抓到阿燐，答案为 $t+1$，即 11.000。

数据范围

本题采用捆绑测试。

对于 30% 的数据，$n\leqslant3$。

对于另外 70% 的数据，$n$，$t\leqslant20$，其中前 40% 的数据和后 30% 的数据分别捆绑测试。

提示

本题主要考察你能否使用正确的方法算出答案，对算法运行耗时要求不高。

by orangebird