403239: GYM101086 K Betrayed

Noura and Judge Mohammad Asaad were in SCS working together when Mohammad decided to betray Noura and leave her to work alone because he couldn't resist participating in the CodeJam.

Noura was very understanding because she knows how much he loves competing. He decided to submit the solution for a problem based on DFS (Depth First Search - See notes below). The input file for this problem contains number of trees with undirected edges and his code will be tested on all of them. After downloading the input file he discovered that his program crashes because of stack overflow, since he must update his code very quickly before the timeout of submitting this problem expires, he decided that instead of starting the DFS from node 1, he will start it from a randomly chosen node (all nodes have the same probability to be chosen).

Assume that the solution takes one second to be run to compute the answer for each tree, if the program crashes it will take Mohammad 3 more seconds to re-run it and in this case the solution should be re-run starting from the first tree.

Mohammad gets stack overflow if the depth of his recursive function exceeds K.

What is the expected number of seconds to pass all trees without getting stack overflow?

The first line of input contains an integer T (1 ≤ T ≤ 128), the number of test cases.

Each test case will start with a line that contains two space - separated integers, C (1 ≤ C ≤ 20), the number of trees of the downloaded input file, and K (1 ≤ K ≤ 10⁵), the maximum depth that does not cause stack overflow. Each of the following C lines represents a tree in the downloaded input file. Each tree is written in the following format:

n a₂ a₃ a₄... a_n, (1 ≤ n ≤ 10⁵), (1 ≤ a_i ≤ n)

Where n is the number of nodes and a_i indicates an undirected edge between a_i and i.

It's guaranteed that in any given tree, at least 25% of its nodes will not cause stack overflow if Mohammad starts the DFS from them.

For each test case print a single number, the expected number of seconds to pass all trees without getting stack overflow, rounded to 4 decimal places.

3
2 2
2 1
3 1 1
3 5
7 3 4 7 1 5 6
6 1 4 2 1 5
5 1 1 5 1
4 3
4 4 1 1
6 1 2 1 1 5
5 4 1 3 4
1

2.0000
4.6000
6.5000

Below is the psuedocode for a recursive implementation of DFS:

  procedure DFS(G,u):
      label u as discovered
      for all edges (u, v) in G do
          if vertex v is not labeled as discovered then
              recursively call DFS(G,v)

The depth of the starting node is 0.

Warning: large Input/Output data, be careful with certain languages.