The nation looks like a connected bidirectional graph, and I am randomly walking on it. It means when I am at node i, I will travel to an adjacent node with the same probability in the next step. I will pick up the start node randomly (each node in the graph
has the same probability.), and travel for d steps, noting that I may go through some nodes multiple times.

If I miss some sights at a node, it will make me unhappy. So I wonder for each node, what is the probability that my path doesn't contain it.

For each test case, the first line contains 3 integers n, m and d, denoting the number of vertices, the number of edges and the number of steps respectively. Then m lines follows, each containing two integers a and b, denoting there is an edge between node
a and node b.

T<=20, n<=50, n-1<=m<=n*(n-1)/2, 1<=d<=10000. There is no self-loops or multiple edges in the graph, and the graph is connected. The nodes are indexed from 1.

Your answer will be accepted if its absolute error doesn't exceed 1e-5.

2
5 10 100
1 2
2 3
3 4
4 5
1 5
2 4
3 5
2 5
1 4
1 3
10 10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
4 9

0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.0000000000
0.6993317967
0.5864284952
0.4440860821
0.2275896991
0.4294074591
0.4851048742
0.4896018842
0.4525044250
0.3406567483
0.6421630037

此题的状态是想到了，但是含义没搞对，本来想把到达某个点的概率求出来，然后用１去减就是答案，但是是不对的，因为那部分概率是有牵连的

设ｄｐ［ｉ］［ｊ］　表示走了ｊ步，目前在节点ｉ，且路径中不含节点ｕ的概率
最后只要累计出节点ｕ以外其他点的概率和就行

/*************************************************************************
    > File Name: hdu4945.cpp
    > Author: ALex
    > Mail: 405045132@qq.com 
    > Created Time: 2014年12月30日 星期二 19时34分57秒
 ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int D = 10010;
const int N = 55;
double dp[N][D];
int n, m, d;
vector <int> edge[N];

void DP(int u)
{
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 0; j <= d; ++j)
		{
			dp[i][j] = 0;
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		dp[i][0] = (1.0 / (double)n);
	}
	for (int i = 0; i < d; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if (j == u)
			{
				continue;
			}
			int cnt = edge[j].size();
			for (int k = 0; k < cnt; ++k)
			{
				int v = edge[j][k];
				if (v == u)
				{
					continue;
				}
				dp[j][i + 1] += dp[v][i] * (1.0 / cnt);
			}
		}
	}
	double ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		if (i == u)
		{
			continue;
		}
		ans += dp[i][d];
	}
	printf("%.10f\n", ans);
}

int main()
{
	int t;
	int u, v;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d%d", &n, &m, &d);
		for (int i = 1; i <= n; ++i)
		{
			edge[i].clear();
		}
		for (int i = 1; i <= m; ++i)
		{
			scanf("%d%d", &u, &v);
			edge[u].push_back(v);
			edge[v].push_back(u);
		}
		for (int i = 1; i <= n; ++i)
		{
			DP(i);
		}
	}
	return 0;
}