求问(有思路,赛时 10 分)

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int,int>;
#define int LL
const int N = 1e5 + 5;
int n, m, k, vis[N];
vector<int> G[N];
inline void read(int& a) {
   int s = 0, w = 1;
   char ch = getchar();
   while (ch < '0' || ch > '9') {
       if (ch == '-') w = -1;
       ch = getchar();
   }
   while (ch >= '0' && ch <= '9') {
       s = s * 10 + ch - '0';
       ch = getchar();
   }
   a = s * w;
}
int splen(int s, int e){
	for(int i = 1; i <= n; ++ i)
		vis[i] = 0;
	vis[s] = 1;
	queue<int> q;
	q.push(s);
	int tot = 0;
	while(!q.empty()){
		int siz = q.size();
		for(int i = 1; i <= siz; ++ i){
			int u = q.front();
//			cout << "tot=" << tot << ",visit " << u << "\n";
			q.pop();
			for(int v: G[u]){
//				cout<<"zijiedian:"<<v<<"\n";
				if(v == e){//cout<<"found "<<v<<"\n";
					return tot + 1;}
				if(!vis[v])
					vis[v] = 1, q.push(v);
			}
		}
		++ tot;
//		cout<<"tot="<<tot<<" start__________\n";
	}
	return -1;
}
signed main(){
	int t;
	read(t);
	while(t --){
		read(n),read(m),read(k);
		for(int i = 1; i <= n; ++ i)
			G[i].clear();
//		cout << "n="<<n<<" m="<<m<<" k="<<k;
		for(int i = 1, u, v; i <= m; ++ i)
			read(u),read(v), G[u].push_back(v), G[v].push_back(u);
		int as, ae, bs, be;
		read(as),read(ae),read(bs),read(be);
//		cout << "cin ended\n";
		int r1 = splen(as, ae), r2 = splen(bs, be);
		if(r1 == -1 || r2 == -1){
			cout << -1;
			continue;
		}
		int tote = r1 + r2;
//		cout << r1 << " " << r2 << "\n";
		int t = k / tote;
		long double ans = 0.0;
		ans += tote * (1.0 / (t + 1)) + (k % tote) * (1.0 / (t + 2) - 1.0 / (t + 1));
        printf("%.12Lf\n",ans);
	}
}