20pts求条

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
const int INF = 0x3f3f3f3f3f3f3f3f;
vector <int> adj[MAXN];
int n, m, s[2], e[2];
int dis[2][MAXN], k;
bool vis[MAXN];
void dijkstra(int o){
	memset(dis[o], 0x3f, sizeof(dis[o]));
	memset(vis, false, sizeof(vis));
	dis[o][s[o]] = 0;
	priority_queue <pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
	q.push({0, s[o]});
	while (!q.empty()){
		int d = q.top().first;
		int u = q.top().second;
		q.pop();
		if (vis[u]){
			continue;
		}
		vis[u] = true;
		for (int v:adj[u]){
			if (dis[o][v] > dis[o][u] + 1){
				dis[o][v] = dis[o][u] + 1;
				q.push({dis[o][v], v});
			}
		}
	}
	return;
}
void solve(){
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++){
		adj[i].clear();
	}
	for (int i = 1; i <= m; i++){
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	cin >> s[0] >> e[0] >> s[1] >> e[1];
	dijkstra(0);
	dijkstra(1);
	int sum = dis[0][e[0]] + dis[1][e[1]];
	if (dis[0][e[0]] > m || dis[1][e[1]] > m){
		cout << "-1" << endl;
		return;
	}
	if (sum == 0){
		cout << sum << endl;
		return;
	}
	int l = k / sum, r = k % sum;
	double ans = 1.0 / (2 + l) * r + 1.0 / (1 + l) * (sum - r);
	printf("%.12lf\n", ans);
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t--){
		solve();
	}
	return 0;
}