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}$ төбелерін қосатын қыр бар екенін білдіретін екі бүтін сан $u_{i,j}$ және $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$) берілген. Бұл қырлардың ағаш құрайтынына кепілдік беріледі.

Шығыс деректер

Тиімді стратегия кезіндегі соққылар санының математикалық күтімін білдіретін бір саннан тұратын бір жолды шығарыңыз.

Егер жауабыңыздың абсолюттік немесе салыстырмалы қателігі $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