Fallleaves01 pała głęboką pasją do golfa, ale niestety jego umiejętności są dość przeciętne.

Aby poprawić swoją grę, Fallleaves01 kupił $k$ domowych trenażerów do puttowania, by ćwiczyć w domu. W przeciwieństwie do zwykłych trenażerów, te, które kupił, są bardzo duże. Dokładniej mówiąc, każdy trenażer można przedstawić jako drzewo o $n_i$ wierzchołkach, gdzie wierzchołek $1$ reprezentuje dołek. Na każdym trenażerze znajduje się piłeczka golfowa. Dla $i$-tego trenażera piłeczka znajduje się początkowo w wierzchołku $s_i$.

Podczas każdego uderzenia Fallleaves01 wybiera jeden trenażer do gry. Ze względu na jego ograniczone umiejętności piłeczka golfowa przemieszcza się losowo z rozkładem jednostajnym do jednego z sąsiednich węzłów. Jeśli piłeczka dotrze do dołka (wierzchołka $1$), trening na dany dzień dobiega końca. W przeciwnym razie Fallleaves01 powtarza powyższy proces, dopóki którakolwiek piłeczka nie wpadnie do dołka.

Celem gracza Fallleaves01 jest zminimalizowanie oczekiwanej liczby uderzeń potrzebnych do zakończenia sesji treningowej. Oblicz oczekiwaną liczbę uderzeń przy założeniu, że przy każdym uderzeniu zawsze dokonuje on najlepszego wyboru.

Wejście

W każdym pliku testowym znajduje się tylko jeden przypadek testowy.

Pierwszy wiersz zawiera liczbę całkowitą $k$ ($1 \le k \le 300$), oznaczającą liczbę domowych trenażerów do puttowania.

Następnie podane są opisy kolejnych trenażerów. Dla każdego trenażera:

• Pierwszy wiersz zawiera dwie liczby całkowite $n_i$ oraz $s_i$ ($2 \le s_i \le n_i \le 300$).
• W kolejnych $(n_i - 1)$ wierszach $j$-ty wiersz zawiera dwie liczby całkowite $u_{i,j}$ oraz $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), oznaczające krawędź łączącą wierzchołki $u_{i,j}$ oraz $v_{i,j}$. Gwarantuje się, że krawędzie te tworzą drzewo.

Wyjście

Wypisz jeden wiersz zawierający jedną liczbę — oczekiwaną liczbę uderzeń przy optymalnej strategii.

Twoja odpowiedź zostanie uznana za poprawną, jeśli jej błąd bezwzględny lub względny nie przekroczy $10^{-6}$. Formalnie, jeśli Twoje wyjście to $a$, a odpowiedź jury to $b$, Twoje wyjście zostanie zaakceptowane wtedy i tylko wtedy, gdy $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Przykład

Uwagi

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

4.666666666666666