Fallleaves01 suhtautuu intohimoisesti golfiin, mutta valitettavasti hänen taitonsa ovat melko keskinkertaiset.

Parantaakseen peliään Fallleaves01 osti $k$ sisäkäyttöön tarkoitettua puttausmattoa harjoitellakseen kotona. Tavallisista harjoitusmatoista poiketen hänen ostamansa matot ovat erittäin suuria. Tarkemmin sanottuna jokainen harjoitusmatto voidaan esittää puuna, jossa on $n_i$ solmua ja jossa solmu $1$ esittää reikää. Jokaisella harjoitusmatolla on golfpallo. $i$-nnellä harjoitusmatolla pallo on aluksi solmussa $s_i$.

Jokaisella lyönnillä Fallleaves01 valitsee yhden harjoitusmaton, jolla hän pelaa. Hänen rajallisen taitotasonsa vuoksi golfpallo siirtyy tasajakautuneesti satunnaiseen viereiseen solmuun. Jos pallo päätyy reikään (solmuun $1$), päivän harjoittelu päättyy. Muussa tapauksessa Fallleaves01 toistaa yllä olevaa prosessia, kunnes jokin pallo menee reikään.

Fallleaves01:n tavoitteena on minimoida harjoituksen päättämiseen tarvittavien lyöntien odotusarvo. Laske lyöntien odotusarvo olettaen, että hän tekee jokaisella lyönnillä aina parhaan valinnan.

Syöte

Jokaisessa testitiedostossa on vain yksi testitapaus.

Ensimmäinen rivi sisältää kokonaisluvun $k$ ($1 \le k \le 300$), joka ilmaisee sisäkäyttöisten puttausmattojen lukumäärän.

Tämän jälkeen seuraavat harjoitusmattojen kuvaukset. Jokaiselle harjoitusmatolle:

• Ensimmäinen rivi sisältää kaksi kokonaislukua $n_i$ ja $s_i$ ($2 \le s_i \le n_i \le 300$).
• Seuraavilla $(n_i - 1)$ rivillä $j$-s rivi sisältää kaksi kokonaislukua $u_{i,j}$ ja $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), mikä tarkoittaa, että solmujen $u_{i,j}$ ja $v_{i,j}$ välillä on kaari. On taattu, että nämä kaaret muodostavat puun.

Tuloste

Tulosta yksi rivi, joka sisältää yhden luvun: lyöntien odotusarvon optimaalisella strategialla.

Vastauksesi katsotaan oikeaksi, jos sen absoluuttinen tai suhteellinen virhe on enintään $10^{-6}$. Muodollisesti, jos tulosteesi on $a$ ja tuomariston vastaus on $b$, tulosteesi hyväksytään jos ja vain jos $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Esimerkit

Huomautus

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

4.666666666666666