Fallleaves01 hefur mikla ástríðu fyrir golfi, en því miður er færni hans frekar í meðallagi.

Til að bæta leik sinn keypti Fallleaves01 $k$ innanhúss púttþjálfa til að æfa sig heima. Ólíkt venjulegum þjálfum eru þeir sem hann keypti mjög stórir. Nánar tiltekið má líta á hvern þjálfa sem tré með $n_i$ hnútum, þar sem hnútur $1$ táknar holuna. Það er golfkúla á hverjum þjálfa. Á $i$-ta þjálfanum er kúlan upphaflega staðsett á hnúti $s_i$.

Í hverju höggi velur Fallleaves01 einn þjálfa til að spila á. Vegna takmarkaðrar færni hans færist golfkúlan af handahófi með jafndreifingu yfir á einn af aðliggjandi hnútum. Ef kúlan nær holunni (hnúti $1$) lýkur æfingunni þann daginn. Annars endurtekur Fallleaves01 ferlið hér að ofan þar til einhver kúla fer ofan í holu.

Markmið Fallleaves01 er að lágmarka væntanlegan fjölda högga sem þarf til að ljúka æfingunni. Reiknaðu væntanlegan fjölda högga, að því gefnu að hann taki alltaf bestu ákvörðunina í hverju höggi.

Inntak

Það er aðeins eitt prófunartilvik í hverri prófunarskrá.

Fyrsta línan inniheldur heiltölu $k$ ($1 \le k \le 300$), sem gefur til kynna fjölda innanhúss púttþjálfa.

Síðan fylgja lýsingar á þjálfunum. Fyrir hvern þjálfa:

• Fyrsta línan inniheldur tvær heiltölur $n_i$ og $s_i$ ($2 \le s_i \le n_i \le 300$).
• Í næstu $(n_i - 1)$ línum inniheldur $j$-ta línan tvær heiltölur $u_{i,j}$ og $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), sem gefur til kynna að leggur tengi saman hnútana $u_{i,j}$ og $v_{i,j}$. Tryggt er að þessir leggir myndi tré.

Úttak

Skrifið út eina línu sem inniheldur eina tölu, sem gefur til kynna væntanlegan fjölda högga samkvæmt bestu mögulegu áætlun.

Svarið þitt telst rétt ef algild eða hlutfallsleg skekkja þess fer ekki yfir $10^{-6}$. Formlega séð, ef úttakið þitt er $a$ og svar dómnefndar er $b$, þá er úttakið þitt samþykkt ef og aðeins ef $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Dæmi

Athugasemd

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

4.666666666666666