Pang 教授在 Capital Grancel 的“城市大脑”项目工作。Grancel 的道路网络可以用一个无向图表示。最初，每条道路的限速均为 $1\,\text{m/s}$。Pang 教授可以花费 $1$ 美元将某条道路的限速提高 $1\,\text{m/s}$。Pang 教授拥有 $k$ 美元。他可以在每条道路上花费任意非负整数金额。如果某条道路的限速为 $a\,\text{m/s}$，则任何人通过该道路（双向）所需的时间为 $1/a$ 秒。

在 Pang 教授花费完他的钱之后，Du 教授开始从城市 $s_1$ 前往城市 $t_1$，Wo 教授开始从城市 $s_2$ 前往城市 $t_2$。请帮助 Pang 教授明智地分配资金，以最小化 Du 教授的最小旅行时间和 Wo 教授的最小旅行时间之和。保证 $s_1$ 与 $t_1$ 之间至少存在一条路径，$s_2$ 与 $t_2$ 之间也至少存在一条路径。

输入格式

第一行包含三个整数 $n, m, k$ ($1 \le n \le 5000, 0 \le m \le 5000, 0 \le k \le 10^9$)，用空格分隔，分别表示图的顶点数、边数以及 Pang 教授拥有的美元数量。

接下来的 $m$ 行，每行包含两个整数 $a, b$ ($1 \le a, b \le n, a \neq b$)，用空格分隔，表示一条道路的两个端点。同一对城市之间可能存在多条道路。

最后一行包含四个整数 $s_1, t_1, s_2, t_2$ ($1 \le s_1, t_1, s_2, t_2 \le n$)，用空格分隔，分别表示 Du 教授和 Wo 教授旅行的起点和终点。

输出格式

输出一行一个小数，表示 Du 教授的旅行时间和 Wo 教授的旅行时间之和的最小值。如果答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

样例

样例输入 1

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

样例输出 1

5.000000000000

样例输入 2

1 0 100
1 1 1 1

样例输出 2

0.000000000000

样例输入 3

4 2 3
1 2
3 4
1 2 3 4

样例输出 3

0.833333333333