题目描述

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

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

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

阿空的目的是尽快捉住阿燐（捉住的定义是与阿燐同一时刻站在同一节点），而阿燐的目的是尽可能更长时间不被阿空捉住。

具体而言，若一场游戏进行了 $t_0$ 时刻，阿燐的得分是 $t_0$，阿空的得分是 $-t_0$，双方都希望自己得分（或得分的期望值）更高。

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

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

输入格式

第一行 $5$ 个整数 $n,m,s_r,s_k,t$，用空格隔开，下同。

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

输出格式

一个实数，四舍五入保留 $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

数据范围与提示

对于 $30\%$ 的数据 $n\le 3$。

对于 $100\%$ 的数据 $1\le n\le 20,0\le t\le 20$。

提示：本题对算法运行耗时要求不高。