يمتلك 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