City Brain

Prof. Pang works for the City Brain program of Capital Grancel. The road network of Grancel is an undirected graph. Initially, the speed limit on each road is $1$ m/s. Prof. Pang can raise the speed limit on a road by $1$ m/s for $1$ dollar. He has $k$ dollars and may spend any nonnegative integer amount on each road.

If a road has speed limit $a$ m/s, anyone can cross it in either direction in $1/a$ seconds. After Prof. Pang spends his money, Prof. Du travels from $s_1$ to $t_1$, and Prof. Wo travels from $s_2$ to $t_2$. Prof. Pang must spend the money so that the sum of the minimum travel times of Prof. Du and Prof. Wo is as small as possible.

It is guaranteed that $s_1$ and $t_1$ are connected by at least one path, and that $s_2$ and $t_2$ are connected by at least one path.

The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le 5000$, $0 \le m \le 5000$, $0 \le k \le 10^9$), separated by single spaces. Here $n$ is the number of vertices, $m$ is the number of edges, and $k$ is the number of dollars.

Each of the next $m$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), the endpoints of one road. Multiple roads may connect the same pair of cities.

The last line contains four integers $s_1$, $t_1$, $s_2$, and $t_2$ ($1 \le s_1, t_1, s_2, t_2 \le n$), the start and end vertices of Prof. Du and Prof. Wo.

Print one real number on a single line: the minimum sum of Prof. Du's and Prof. Wo's travel times. The answer is accepted if its absolute or relative error does not exceed $10^{-9}$.