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 ≤ 105), 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 a2 a3 a4... an, (1 ≤ n ≤ 105), (1 ≤ ai ≤ n)
Where n is the number of nodes and ai indicates an undirected edge between ai 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.
Below is the psuedocode for a recursive implementation of DFS:
The depth of the starting node is 0.
Warning: large Input/Output data, be careful with certain languages.
## Input
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 ≤ 105), 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 a2 a3 a4... an, (1 ≤ n ≤ 105), (1 ≤ ai ≤ n)Where n is the number of nodes and ai indicates an undirected edge between ai 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.
## Output
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.
[samples]
## Note
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.
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ C \in \mathbb{Z} $ be the number of trees.
- Let $ K \in \mathbb{Z} $ be the maximum allowed DFS depth (stack overflow threshold).
- For each tree $ j \in \{1, \dots, C\} $, let $ G_j = (V_j, E_j) $ be an undirected tree with $ n_j = |V_j| $ nodes and edges defined by input $ a_2, a_3, \dots, a_{n_j} $, where edge $ (i, a_i) $ exists for $ i = 2, \dots, n_j $.
Let $ S_j \subseteq V_j $ be the set of nodes from which starting DFS results in maximum depth $ \leq K $ (i.e., no stack overflow).
Let $ p_j = \frac{|S_j|}{n_j} $ be the probability that a randomly chosen starting node for tree $ j $ avoids stack overflow.
**Constraints**
1. $ 1 \leq T \leq 128 $
2. $ 1 \leq C \leq 20 $
3. $ 1 \leq K \leq 10^5 $
4. $ 1 \leq n_j \leq 10^5 $ for each tree $ j $
5. $ p_j \geq 0.25 $ for all $ j \in \{1, \dots, C\} $
**Objective**
Compute the expected total time (in seconds) to successfully process all $ C $ trees without stack overflow, where:
- Each successful DFS run takes 1 second.
- A stack overflow causes a 3-second penalty and forces restart from tree 1.
- Starting nodes are chosen uniformly at random per tree.
Let $ X $ be the total expected time.
For each tree $ j $, the probability of success is $ p_j $, and failure is $ 1 - p_j $.
The process succeeds only if all $ C $ trees are processed without failure.
The expected time satisfies:
$$
X = \left( \sum_{j=1}^{C} 1 \right) + \left( \prod_{j=1}^{C} p_j \right)^{-1} \cdot \left( \sum_{i=1}^{C} \left( \prod_{k=1}^{i-1} p_k \right) (1 - p_i) \cdot 3 \right)
$$
Alternatively, using the recurrence for geometric retry:
Let $ P = \prod_{j=1}^{C} p_j $ be the probability of successfully completing all $ C $ trees in one full attempt.
Each full attempt takes $ C $ seconds, and with probability $ 1 - P $, it fails and incurs an additional 3 seconds penalty before retrying.
The expected number of full attempts is $ \frac{1}{P} $.
Each failed attempt (except the last success) incurs a 3-second penalty.
The expected number of failed attempts is $ \frac{1 - P}{P} $.
Thus:
$$
X = \frac{C}{P} + 3 \cdot \frac{1 - P}{P}
$$
$$
\boxed{X = \frac{C + 3(1 - P)}{P} \quad \text{where} \quad P = \prod_{j=1}^{C} p_j}
$$