Fallleaves01 memiliki hasrat yang mendalam terhadap olahraga golf, tetapi sayangnya, kemampuannya cukup biasa-biasa saja.

Untuk meningkatkan permainannya, Fallleaves01 membeli $k$ alat latihan putting golf dalam ruangan untuk berlatih di rumah. Berbeda dengan alat latihan biasa, alat yang ia beli berukuran sangat besar. Secara spesifik, setiap alat latihan dapat diabstraksikan sebagai sebuah pohon dengan $n_i$ titik, di mana titik $1$ merepresentasikan lubang golf. Terdapat sebuah bola golf pada setiap alat latihan. Untuk alat latihan ke-$i$, bola awalnya ditempatkan pada titik $s_i$.

Pada setiap pukulan, Fallleaves01 memilih satu alat latihan untuk dimainkan. Karena tingkat kemampuannya yang terbatas, bola golf akan bergerak secara acak seragam ke salah satu simpul yang bertetangga. Jika bola mencapai lubang (titik $1$), sesi latihan hari itu berakhir. Jika tidak, Fallleaves01 mengulangi proses di atas hingga ada bola yang masuk ke lubang.

Tujuan Fallleaves01 adalah meminimalkan nilai ekspektasi jumlah pukulan yang diperlukan untuk menyelesaikan sesi latihan. Hitunglah nilai ekspektasi jumlah pukulan, dengan asumsi ia selalu membuat pilihan terbaik pada setiap pukulan.

Masukan

Hanya terdapat satu kasus uji dalam setiap berkas uji.

Baris pertama berisi sebuah bilangan bulat $k$ ($1 \le k \le 300$), yang menyatakan jumlah alat latihan putting golf dalam ruangan.

Kemudian, deskripsi untuk setiap alat latihan menyusul. Untuk setiap alat latihan:

• Baris pertama berisi dua bilangan bulat $n_i$ dan $s_i$ ($2 \le s_i \le n_i \le 300$).
• Untuk $(n_i - 1)$ baris berikutnya, baris ke-$j$ berisi dua bilangan bulat $u_{i,j}$ dan $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), yang menyatakan bahwa terdapat sisi yang menghubungkan titik $u_{i,j}$ dan $v_{i,j}$. Dijamin bahwa sisi-sisi ini membentuk sebuah pohon.

Keluaran

Keluarkan satu baris yang berisi satu bilangan, yang menyatakan nilai ekspektasi jumlah pukulan di bawah strategi optimal.

Jawaban Anda akan dianggap benar jika galat absolut atau relatifnya tidak melebihi $10^{-6}$. Secara formal, misalkan keluaran Anda adalah $a$ dan jawaban juri adalah $b$, keluaran Anda diterima jika dan hanya jika $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Contoh

Catatan

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

4.666666666666666