Fallleaves01은 골프에 깊은 열정을 가지고 있지만, 안타깝게도 그의 실력은 평범한 편입니다.

실력을 키우기 위해 Fallleaves01은 집에서 연습할 실내 골프 퍼팅 연습기 $k$개를 구매했습니다. 일반 연습기와 달리 그가 구매한 연습기는 매우 거대합니다. 구체적으로, 각 연습기는 $n_i$개의 정점으로 이루어진 트리로 추상화할 수 있으며, 정점 $1$은 홀(구멍)을 나타냅니다. 각 연습기 위에는 골프공이 하나씩 놓여 있습니다. $i$번째 연습기에서 공은 처음에 정점 $s_i$에 놓여 있습니다.

매 타수마다 Fallleaves01은 연습기 하나를 골라 공을 칩니다. 그의 실력이 부족하기 때문에, 골프공은 인접한 노드 중 하나로 균등하게 무작위로 이동합니다. 만약 공이 홀(정점 $1$)에 도달하면 그날의 연습은 종료됩니다. 그렇지 않으면 어느 공이든 홀에 들어갈 때까지 위 과정을 반복합니다.

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