题目传送门
#include<bits/stdc++.h>
using namespace std;
int t,n,m,tot;
int nbs[50050];
bool vis[100050];
int dis[50050];
int cnt[50050];
int cntt[50050];
struct edge{
int ed,next;
}b[100050];
struct node{
int x,step;
}s;
void add(int x,int y){
tot++;
b[tot].ed=y;
b[tot].next=nbs[x];
nbs[x]=tot;
}
void bfs(){
queue<node>q;
q.push({1,0});
vis[1]=1;
while(!q.empty()){
s=q.front();
q.pop();
dis[s.x]=s.step;
for(int x=nbs[s.x];x;x=b[x].next){
int u=b[x].ed;
if(!vis[u]){
q.push({u,s.step+1});
vis[u]=1;
}
}
}
}
void dfs(int k,int fa,int step){
cnt[k]++;
if(step==dis[k])cntt[k]++;
for(int x=nbs[k];x;x=b[x].next){
if(vis[x])continue;
vis[x]=1;
int u=b[x].ed;
if(u!=fa)dfs(u,k,step+1);
}
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
memset(nbs,0,sizeof(nbs));
memset(vis,0,sizeof(vis));
memset(dis,-1,sizeof(dis));
memset(cnt,0,sizeof(cnt));
memset(cntt,0,sizeof(cntt));
tot=0;
for(int i=1,x,y;i<=m;i++){
cin>>x>>y;
add(x,y);
add(y,x);
}
bfs();
memset(vis,0,sizeof(vis));
dfs(1,0,0);
double ans=1;
for(int i=1;i<=n;i++){
if(cnt[i]==0)continue;
// cout<<cntt[i]<<' '<<cnt[i]<<endl;
ans*=(double)cntt[i]/cnt[i];
}
printf("%.3lf\n",ans);
}
return 0;
}