求 hack

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
int n, m, k, dst[5005][5005], q[5005], front, rear, s1, s2, t1, t2, dp[5005][5005], res[5005];
vector<int> edges[5005];

void bfs(int s, int *dst) {
	front = 1, rear = 0;
	for (int i = 1; i <= n; ++i) {
		dst[i] = 1ll << 60;
	}
	q[++rear] = s;
	dst[s] = 0;
	while (rear + 1 != front) {
		int fx = q[front++];
		for (auto j : edges[fx]) {
			if (dst[j] == 1ll << 60) {
				dst[j] = dst[fx] + 1;
				q[++rear] = j;
			}
		}
	}
}


double get_ans(int t, int s, int ta, int ts) {
	// t -> 相同路径
	// s -> 不相同路径
	assert(ta >= 0);
	assert(ts >= 0);
	assert(ta + ts == k);
	return (t ? ((double)1.0 / (ta / t + 2) * (ta % t) +
		   (double)1.0 / (ta / t + 1) * (t - ta % t)) * 2 : 0) +
	       (s ? (double)1.0 / (ts / s + 2) * (ts % s) +
		   (double)1.0 / (ts / s + 1) * (s - ts % s) : 0);
}

const int L = 10;

double get_s(int t, int s) {
	int l = 0, r = k;
	double ans = 1e308;
	while (r - l > L) {
		int mid1 = l + (r - l) / 3, mid2 = l + (r - l) / 3 * 2;
		double ans1 = get_ans(t, s, mid1, k - mid1);
		double ans2 = get_ans(t, s, mid2, k - mid2);
		ans = min({ans, ans1, ans2});
		if (ans1 > ans2) l = mid1;
		else r = mid2;
	} 
	for (int i = max(l - L, 0ll); i <= min(r + L, k); ++i) {
		ans = min(ans, get_ans(t, s, i, k - i));
	}
	return ans;
}


signed main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= m; ++i) {
		int u, v;;
		cin >> u >> v;
		edges[u].push_back(v);
		edges[v].push_back(u);
	}
	cin >> s1 >> t1 >> s2 >> t2;
	for (int i = 1; i <= n; ++i) {
		bfs(i, dst[i]);
	}
	memset(res, 1, sizeof(res));
	res[0] = dst[s1][t1] + dst[s2][t2];
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			if (dst[i][j] <= 5000 && dst[s1][i] <= 5000 && dst[j][t1] <= 5000 && dst[s2][i] <= 5000 && dst[j][t2] <= 5000) {
				res[dst[i][j]] = min(res[dst[i][j]], dst[s1][i] + dst[j][t1] + dst[s2][i] + dst[j][t2]);
			}
		}
	}
	double ans = 1e308;
	for (int i = 0; i <= 5000; ++i) {
		if (res[i] <= 12000) {
			ans = min(ans, get_s(i, res[i]));
		}
	}
	printf("%.15Lf\n", ans);
	return 0;
}