ל-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