Fallleaves01 voue une profonde passion au golf, mais malheureusement, son niveau est plutôt moyen.

Pour améliorer son jeu, Fallleaves01 a acheté $k$ tapis d'entraînement de putting d'intérieur pour s'exercer chez lui. Contrairement aux tapis ordinaires, ceux qu'il a achetés sont très grands. Plus précisément, chaque tapis d'entraînement peut être modélisé par un arbre à $n_i$ sommets, où le sommet $1$ représente le trou. Il y a une balle de golf sur chaque tapis. Pour le $i$-ème tapis, la balle est initialement placée au sommet $s_i$.

À chaque coup, Fallleaves01 choisit un tapis sur lequel jouer. En raison de son niveau limité, la balle de golf se déplace uniformément au hasard vers l'un des nœuds adjacents. Si la balle atteint le trou (le sommet $1$), la séance d'entraînement se termine pour la journée. Sinon, Fallleaves01 répète le processus ci-dessus jusqu'à ce qu'une balle entre dans un trou.

L'objectif de Fallleaves01 est de minimiser l'espérance du nombre de coups nécessaires pour terminer la séance d'entraînement. Calculez l'espérance du nombre de coups, en supposant qu'il fasse toujours le meilleur choix à chaque coup.

Entrée

Il n'y a qu'un seul cas de test dans chaque fichier de test.

La première ligne contient un entier $k$ ($1 \le k \le 300$), indiquant le nombre de tapis d'entraînement de putting d'intérieur.

Ensuite, les descriptions des tapis suivent. Pour chaque tapis :

• La première ligne contient deux entiers $n_i$ et $s_i$ ($2 \le s_i \le n_i \le 300$).
• Pour les $(n_i - 1)$ lignes suivantes, la $j$-ème ligne contient deux entiers $u_{i,j}$ et $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), indiquant qu'il existe une arête reliant les sommets $u_{i,j}$ et $v_{i,j}$. Il est garanti que ces arêtes forment un arbre.

Sortie

Affichez une ligne contenant un seul nombre, indiquant l'espérance du nombre de coups sous la stratégie optimale.

Votre réponse sera considérée comme correcte si son erreur absolue ou relative ne dépasse pas $10^{-6}$. Formellement, en supposant que votre sortie soit $a$ et que la réponse du jury soit $b$, votre sortie est acceptée si et seulement si $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Exemples

Remarque

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

4.666666666666666