Optimizing Road Speed Limits for Minimizing Travel Time Sum

Professor Pang is tasked with optimizing the road network of Capital Grancel. The road network is given as an undirected graph with n cities and m roads. Initially, each road has a speed limit of \(1\) m/s. Professor Pang can invest dollars to increase the speed limit on any road. Spending \(1\) dollar on a road increases its speed limit by \(1\) m/s. If a road’s speed limit is \(a\) m/s, it takes \(1/a\) seconds to travel it in either direction. He has a budget of \(k\) dollars and may spend any nonnegative integral amount on each road (with the total spending not exceeding \(k\)).

After the improvements, Professor Du will travel from city \(s_1\) to \(t_1\) and Professor Wo will travel from city \(s_2\) to \(t_2\). Each professor chooses the fastest (i.e. minimum time) path available in the adjusted road network. The goal is to decide how to distribute the \(k\) dollars among the roads to minimize the sum of the travel times for the two professors. Formally, if an edge has \(d\) dollars invested, its travel time becomes \(\frac{1}{1+d}\) seconds. Let the minimum travel times be \[ T_1 = \min_{P:\,s_1\to t_1} \sum_{e\in P} \frac{1}{1+d_e}, \quad T_2 = \min_{P:\,s_2\to t_2} \sum_{e\in P} \frac{1}{1+d_e}, \] find an allocation \(\{ d_e \}\) (with \(d_e \in \mathbb{Z}_{\ge0}\) and \(\sum_{e} d_e \le k\)) such that \(T_1 + T_2\) is minimized.

Note: It is guaranteed that there is at least one path between \(s_1\) and \(t_1\) and at least one path between \(s_2\) and \(t_2\).

inputFormat

The first line of input contains three integers \(n\), \(m\) and \(k\) -- the number of cities, the number of roads and the available dollars respectively.

The next \(m\) lines each contain two integers \(u\) and \(v\), indicating that there is an undirected road connecting cities \(u\) and \(v\). (Cities are 1-indexed.)

The following line contains two integers \(s_1\) and \(t_1\) representing the start and the destination for Professor Du.

The last line contains two integers \(s_2\) and \(t_2\) representing the start and the destination for Professor Wo.

outputFormat

Output a single number: the minimum possible sum of the travel times for the two professors. Output your answer with at least 6 digits after the decimal point.

sample

3 3 1
1 2
2 3
1 3
1 3
2 3

1.500000