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