Fallleaves01 har en djup passion för golf, men tyvärr är hans färdigheter ganska genomsnittliga.

För att förbättra sitt spel köpte Fallleaves01 $k$ inomhusmattor för puttträning för att öva hemma. Till skillnad från vanliga träningsredskap är de han köpte väldigt stora. Mer specifikt kan varje träningsredskap abstraheras som ett träd med $n_i$ hörn, där hörn $1$ representerar hålet. Det finns en golfboll på varje träningsredskap. För det $i$-te träningsredskapet är bollen från början placerad vid hörn $s_i$.

Vid varje slag väljer Fallleaves01 ett träningsredskap att spela på. På grund av hans begränsade skicklighet kommer golfbollen att förflytta sig likformigt slumpmässigt till en av de intilliggande noderna. Om bollen når hålet (hörn $1$) avslutas träningspasset för dagen. Annars upprepar Fallleaves01 processen ovan tills någon boll går i hål.

Målet för Fallleaves01 är att minimera det förväntade antalet slag som krävs för att avsluta träningspasset. Beräkna det förväntade antalet slag under antagandet att han alltid gör det bästa valet vid varje slag.

Indata

Det finns bara ett testfall i varje testfil.

Den första raden innehåller ett heltal $k$ ($1 \le k \le 300$), som anger antalet inomhusredskap för puttträning.

Därefter följer beskrivningarna av träningsredskapen. För varje träningsredskap:

• Den första raden innehåller två heltal $n_i$ och $s_i$ ($2 \le s_i \le n_i \le 300$).
• På de följande $(n_i - 1)$ raderna innehåller den $j$-te raden två heltal $u_{i,j}$ och $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), vilket anger att det finns en kant som förbinder hörnen $u_{i,j}$ och $v_{i,j}$. Det garanteras att dessa kanter bildar ett träd.

Utdata

Skriv ut en rad som innehåller ett tal, vilket anger det förväntade antalet slag under den optimala strategin.

Ditt svar betraktas som korrekt om dess absoluta eller relativa fel inte överstiger $10^{-6}$. Formellt sett, anta att din utdata är $a$ och juryns svar är $b$; din utdata accepteras om och endast om $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Exempel

Notering

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

4.666666666666666