Fallleaves01 hat eine tiefe Leidenschaft für Golf, aber leider sind seine Fähigkeiten eher durchschnittlich.

Um sein Spiel zu verbessern, hat Fallleaves01 $k$ Indoor-Golf-Putting-Trainer für das Training zu Hause gekauft. Im Gegensatz zu gewöhnlichen Trainern sind die von ihm gekauften sehr groß. Genauer gesagt lässt sich jeder Trainer als ein Baum mit $n_i$ Knoten abstrahieren, wobei Knoten $1$ das Loch darstellt. Auf jedem Trainer befindet sich ein Golfball. Beim $i$-ten Trainer liegt der Ball anfangs auf Knoten $s_i$.

Bei jedem Schlag wählt Fallleaves01 einen Trainer zum Spielen aus. Aufgrund seines begrenzten Könnens bewegt sich der Golfball gleichverteilt zufällig zu einem der benachbarten Knoten. Erreicht der Ball das Loch (Knoten $1$), ist die Trainingseinheit für diesen Tag beendet. Andernfalls wiederholt Fallleaves01 den obigen Vorgang, bis irgendein Ball in ein Loch fällt.

Das Ziel von Fallleaves01 ist es, die erwartete Anzahl an Schlägen bis zum Ende der Trainingseinheit zu minimieren. Berechnen Sie die erwartete Anzahl an Schlägen unter der Annahme, dass er bei jedem Schlag stets die beste Wahl trifft.

Eingabe

Jede Testdatei enthält nur einen einzigen Testfall.

Die erste Zeile enthält eine ganze Zahl $k$ ($1 \le k \le 300$), die die Anzahl der Indoor-Golf-Putting-Trainer angibt.

Anschließend folgen die Beschreibungen der Trainer. Für jeden Trainer gilt:

• Die erste Zeile enthält zwei ganze Zahlen $n_i$ und $s_i$ ($2 \le s_i \le n_i \le 300$).
• In den folgenden $(n_i - 1)$ Zeilen enthält die $j$-te Zeile zwei ganze Zahlen $u_{i,j}$ und $v_{i,j}$ ($1 \le u_{i,j}, v_{i,j} \le n_i$), was bedeutet, dass eine Kante zwischen den Knoten $u_{i,j}$ und $v_{i,j}$ verläuft. Es wird garantiert, dass diese Kanten einen Baum bilden.

Ausgabe

Geben Sie eine Zeile mit einer einzigen Zahl aus, die die erwartete Anzahl an Schlägen unter der optimalen Strategie angibt.

Ihre Antwort gilt als korrekt, wenn ihr absoluter oder relativer Fehler $10^{-6}$ nicht überschreitet. Formal ausgedrückt: Sei $a$ Ihre Ausgabe und $b$ die Antwort der Jury, dann wird Ihre Ausgabe genau dann akzeptiert, wenn $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ gilt.

Beispiele

Hinweis

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

4.666666666666666