Migrated from Lutece 2982 修路

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

verjun 正在为市政府提出城市路径修建的规划。 城市内部的路径布局可以看作一个 $n$ 个点 $m$ 条边的无向图，初始每条边的限速为 $1\text{m/s}$。verjun 可以花费 $1$ 的代价选择一条边把它的限速提升 $1\text{m/s}$。每条边的长度均为 $1\text m$，如果某条边的限速是 $a\text{m/s}$，则通过这条边的时间为 $\frac 1a\text s$。 市政府最多可承受 $k$ 的代价，而且 verjun 可以在每条边上花费任意非负的代价以提高这条边的限速。 调研发现这座城市中人们经过最频繁的路径有两条，分别以 $s_1,s_2$ 为起点，$t_1,t_2$ 为终点，verjun 想知道修改限速后通过这两条路径的时间之和的最小值。

Input

第一行包含三个整数 $n,m,k(1\le n\le 5000,0\le m\le 5000, 0\le k\le 10^8)$，分别代表图的点数，边数以及最高能承受的代价。 接下来 $m$ 行每行两个整数 $a,b(1\le a,b\le n, a\not=b)$，代表一条从点 $a$ 到点 $b$ 的无向边，可能会有重边。 最后一行包含四个整数 $s_1,t_1,s_2,t_2$，分别代表两条路径的起止点。

Output

输出一个浮点数，代表通过这两条路径的时间之和的最小值。 请保留9位小数

Samples

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

5.000000000

4 2 3
1 2
3 4
1 2 3 4

0.833333333333

Resources

2023 UESTC ICPC Training for Graph