Fallleaves01 har en dyp lidenskap for golf, men dessverre er ferdighetene hans heller gjennomsnittlige.

For å forbedre spillet sitt kjøpte Fallleaves01 $k$ innendørs puttetrenere for å øve hjemme. I motsetning til vanlige trenere er de han kjøpte svært store. Mer spesifikt kan hver trener abstraheres som et tre med $n_i$ noder, der node $1$ representerer hullet. Det ligger en golfball på hver trener. For den $i$-te treneren er ballen opprinnelig plassert på node $s_i$.

Under hvert slag velger Fallleaves01 én trener å spille på. På grunn av hans begrensede ferdighetsnivå vil golfballen bevege seg uniformt tilfeldig til en av nabonodene. Hvis ballen når hullet (node $1$), avsluttes treningsøkten for dagen. Ellers gjentar Fallleaves01 prosessen ovenfor helt til en eller annen ball går i et hull.

Målet til Fallleaves01 er å minimere det forventede antallet slag som kreves for å fullføre treningsøkten. Beregn det forventede antallet slag, gitt at han alltid tar det beste valget ved hvert slag.

Inndata

Det er bare ett testtilfelle i hver testfil.

Den første linjen inneholder et heltall $k$ ($1 \le k \le 300$), som angir antallet innendørs puttetrenere.

Deretter følger beskrivelsene av trenerne. For hver trener:

• Den første linjen inneholder to heltall $n_i$ og $s_i$ ($2 \le s_i \le n_i \le 300$).
• I de følgende $(n_i - 1)$ linjene inneholder den $j$-te linjen to heltall $u_{i,j}$ og $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), som angir at det går en kant mellom nodene $u_{i,j}$ og $v_{i,j}$. Det er garantert at disse kantene danner et tre.

Utdata

Skriv ut én linje som inneholder ett tall, som angir det forventede antallet slag under den optimale strategien.

Svaret ditt vil bli regnet som riktig hvis det absolutte eller relative avviket ikke overstiger $10^{-6}$. Formelt sett, anta at utskriften din er $a$ og juryens svar er $b$; utskriften din godtas hvis og bare hvis $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Eksempler

Merk

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

4.666666666666666