Expected Same-Color Edges

You are given an undirected graph with N vertices and M edges. Each vertex is independently assigned a color uniformly at random from C available colors. For any edge connecting vertices u and v, the probability that both endpoints have the same color is \(\frac{1}{C}\). Thus, the expected number of edges with both endpoints having the same color is given by \(\frac{M}{C}\>.

Although the actual graph structure (i.e. the list of edges) is provided, the result depends solely on M and C. Your task is to compute the expected number of same-color edges using the formula \(\frac{M}{C}\) for each given test case.

inputFormat

The first line contains an integer T, the number of test cases. For each test case, the first line contains three integers: N (the number of vertices), M (the number of edges), and C (the number of colors). This is followed by M lines, each containing two integers u and v, representing an edge between vertices u and v.

outputFormat

For each test case, output a single line containing a floating-point number, which is the expected number of edges whose endpoints have the same color. The answer should be accurate up to at least 10 decimal places.

3
3 3 2
1 2
2 3
1 3
4 4 3
1 2
2 3
3 4
4 1
5 5 5
1 2
2 3
3 4
4 5
5 1

1.5000000000
1.3333333333
1.0000000000