Fallleaves01 has a deep passion for golf, but unfortunately, his skills are rather average.

To improve his game, Fallleaves01 purchased $k$ indoor golf putting trainers for practicing at home. Unlike ordinary trainers, the ones he bought are very large. Specifically, each trainer can be abstracted as a tree with $n_i$ vertices, where vertex $1$ represents the hole. There is a golf ball on each trainer. For the $i$-th trainer, the ball is initially placed at vertex $s_i$.

During each stroke, Fallleaves01 chooses one trainer to play. Due to his limited skill level, the golf ball will move uniformly at random to one of the adjacent nodes. If the ball reaches the hole (vertex $1$), the practice session ends for the day. Otherwise, Fallleaves01 repeats the above process until any ball enters a hole.

Fallleaves01's goal is to minimize the expected number of strokes required to finish the practice session. Calculate the expected number of strokes, assuming he always makes the best choice for each stroke.

Input

There is only one test case in each test file.

The first line contains an integer $k$ ($1 \le k \le 300$), indicating the number of indoor golf putting trainers.

Then, the descriptions for the trainers follow. For each trainer:

• The first line contains two integers $n_i$ and $s_i$ ($2 \le s_i \le n_i \le 300$).
• For the following $(n_i - 1)$ lines, the $j$-th line contains two integers $u_{i,j}$ and $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), indicating that there is an edge connecting vertices $u_{i,j}$ and $v_{i,j}$. It is guaranteed that these edges form a tree.

Output

Output one line containing one number, indicating the expected number of strokes under the optimal strategy.

Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$. Formally speaking, suppose that your output is $a$ and the jury's answer is $b$, your output is accepted if and only if $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Examples

Note

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

4.666666666666666