Fallleaves01 có niềm đam mê sâu sắc với môn đánh gôn, nhưng thật không may, kỹ năng của anh ấy chỉ ở mức trung bình.

Để cải thiện trình độ, Fallleaves01 đã mua $k$ bộ dụng cụ tập gạt bóng gôn trong nhà để luyện tập. Khác với những bộ dụng cụ thông thường, những bộ mà anh ấy mua có kích thước rất lớn. Cụ thể, mỗi bộ tập có thể được trừu tượng hóa thành một cây gồm $n_i$ đỉnh, trong đó đỉnh $1$ biểu thị lỗ gôn. Trên mỗi bộ tập có một quả bóng gôn. Đối với bộ tập thứ $i$, quả bóng ban đầu được đặt tại đỉnh $s_i$.

Trong mỗi cú đánh, Fallleaves01 chọn một bộ tập để chơi. Do trình độ có hạn, quả bóng gôn sẽ di chuyển ngẫu nhiên phân bố đều sang một trong các nút kề với nó. Nếu quả bóng đi đến lỗ gôn (đỉnh $1$), buổi tập trong ngày sẽ kết thúc. Ngược lại, Fallleaves01 lặp lại quá trình trên cho đến khi có bất kỳ quả bóng nào rơi vào lỗ.

Mục tiêu của Fallleaves01 là cực tiểu hóa số cú đánh kỳ vọng cần thiết để hoàn thành buổi tập. Hãy tính số cú đánh kỳ vọng, giả sử rằng anh ấy luôn đưa ra lựa chọn tốt nhất ở mỗi cú đánh.

Dữ liệu vào

Mỗi tệp dữ liệu chỉ chứa một bộ dữ liệu.

Dòng đầu tiên chứa một số nguyên $k$ ($1 \le k \le 300$), cho biết số lượng bộ dụng cụ tập gạt bóng gôn trong nhà.

Tiếp theo là phần mô tả cho từng bộ tập. Đối với mỗi bộ tập:

• Dòng đầu tiên chứa hai số nguyên $n_i$ và $s_i$ ($2 \le s_i \le n_i \le 300$).
• Trong $(n_i - 1)$ dòng tiếp theo, dòng thứ $j$ chứa hai số nguyên $u_{i,j}$ và $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), cho biết có một cạnh nối hai đỉnh $u_{i,j}$ và $v_{i,j}$. Dữ liệu đảm bảo các cạnh này tạo thành một cây.

Dữ liệu ra

In ra một dòng chứa một số duy nhất, cho biết số cú đánh kỳ vọng theo chiến lược tối ưu.

Câu trả lời của bạn sẽ được coi là đúng nếu sai số tuyệt đối hoặc tương đối không vượt quá $10^{-6}$. Nói cách khác, giả sử kết quả của bạn là $a$ và đáp án của ban giám khảo là $b$, kết quả của bạn được chấp nhận khi và chỉ khi $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$.

Ví dụ

Ghi chú

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

4.666666666666666