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