Fallleaves01 ha una profonda passione per il golf, ma sfortunatamente le sue abilità sono piuttosto nella media.

Per migliorare il suo gioco, Fallleaves01 ha acquistato $k$ allenatori da putting per il golf indoor per esercitarsi a casa. A differenza dei normali allenatori, quelli che ha comprato sono molto grandi. Nello specifico, ogni allenatore può essere astratto come un albero con $n_i$ vertici, dove il vertice $1$ rappresenta la buca. Su ogni allenatore c'è una pallina da golf. Per l'$i$-esimo allenatore, la pallina è inizialmente posizionata sul vertice $s_i$.

Durante ogni colpo, Fallleaves01 sceglie un allenatore su cui giocare. A causa del suo livello di abilità limitato, la pallina da golf si sposterà in modo casuale e uniforme verso uno dei nodi adiacenti. Se la pallina raggiunge la buca (vertice $1$), la sessione di allenamento termina per la giornata. Altrimenti, Fallleaves01 ripete il processo sopra descritto finché una pallina qualsiasi non entra in una buca.

L'obiettivo di Fallleaves01 è minimizzare il numero atteso di colpi necessari per terminare la sessione di allenamento. Calcola il numero atteso di colpi, supponendo che faccia sempre la scelta migliore a ogni colpo.

Input

C'è un solo caso di test in ciascun file di test.

La prima riga contiene un intero $k$ ($1 \le k \le 300$), che indica il numero di allenatori da putting per il golf indoor.

Seguono poi le descrizioni degli allenatori. Per ciascun allenatore:

• La prima riga contiene due interi $n_i$ e $s_i$ ($2 \le s_i \le n_i \le 300$).
• Nelle successive $(n_i - 1)$ righe, la $j$-esima riga contiene due interi $u_{i,j}$ e $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), a indicare che c'è un arco che collega i vertici $u_{i,j}$ e $v_{i,j}$. È garantito che questi archi formino un albero.

Output

Stampa una riga contenente un solo numero, che indica il numero atteso di colpi seguendo la strategia ottimale.

La tua risposta sarà considerata corretta se il suo errore assoluto o relativo non supera $10^{-6}$. Formalmente, supponendo che il tuo output sia $a$ e la risposta della giuria sia $b$, il tuo output è accettato se e solo se $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Esempi

Note

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

4.666666666666666