Fallleaves01 має глибоку пристрасть до гольфу, але, на жаль, його навички досить посередні.

Щоб покращити свою гру, Fallleaves01 придбав $k$ домашніх тренажерів для патингу, щоб тренуватися вдома. На відміну від звичайних тренажерів, ті, які він купив, дуже великі. Зокрема, кожен тренажер можна абстрактно подати як дерево з $n_i$ вершинами, де вершина $1$ відповідає лунці. На кожному тренажері є м'яч для гольфу. На $i$-му тренажері м'яч спочатку розміщений у вершині $s_i$.

Під час кожного удару Fallleaves01 вибирає один тренажер для гри. Через його обмежений рівень майстерності м'яч для гольфу рівноймовірно переміщується в один із сусідніх вузлів. Якщо м'яч досягає лунки (вершини $1$), тренування на цей день закінчується. Інакше Fallleaves01 повторює описаний вище процес, доки будь-який м'яч не потрапить у лунку.

Мета Fallleaves01 — мінімізувати математичне сподівання кількості ударів, необхідних для завершення тренування. Обчисліть очікувану кількість ударів за умови, що на кожному ударі він завжди робить найкращий вибір.

Вхідні дані

У кожному тестовому файлі міститься лише один тестовий випадок.

Перший рядок містить ціле число $k$ ($1 \le k \le 300$), що означає кількість домашніх тренажерів для патингу.

Далі йдуть описи тренажерів. Для кожного тренажера:

• Перший рядок містить два цілі числа $n_i$ та $s_i$ ($2 \le s_i \le n_i \le 300$).
• У наступних $(n_i - 1)$ рядках $j$-й рядок містить два цілі числа $u_{i,j}$ та $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), які вказують на наявність ребра, що з'єднує вершини $u_{i,j}$ та $v_{i,j}$. Гарантується, що ці ребра утворюють дерево.

Вихідні дані

Виведіть один рядок, що містить одне число — очікувану кількість ударів за оптимальної стратегії.

Ваша відповідь вважатиметься правильною, якщо її абсолютна або відносна похибка не перевищує $10^{-6}$. Формально кажучи, припустімо, що ваш вивід дорівнює $a$, а відповідь журі дорівнює $b$; ваш вивід приймається тоді й лише тоді, коли $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Приклади

Примітка

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

4.666666666666666