Length Of Cycle

頂点数の木が与えられます。個の頂点はそれぞれ番号からまでを用いて表せるものとします。

行にわたって、入力が与えられ、個目の入力では、頂点と頂点が辺で繋がれているということが伝えられます。

グラフが好きなモジャくんは木を見て、以下のことに気が付きました。

◉「異なる頂点を選択して、点の間に（元々辺が存在するかに関わらず)新しい辺を結ぶと、ちょうどつだけ閉路ができる。」

モジャくんは、気になってできる閉路の長さの期待値を考えましたが、他の課題が迫っている中、落ち着いて考えることができませんでした。

モジャくんの代わりに閉路の長さの期待値を求めてください。

なお、ここでの期待値は、考えうる全てののペア通りに対する、閉路の長さの平均値と解釈できます。

・

・

・与えられるグラフは木である。

・入力は全て整数値である。

N
a_1 b_1
a_2 b_2
.
.
.
a_(N-1) b_(N-1)

この問題の条件下では、求める期待値に対し

・

・

なる自然数のペアが一意に存在します。

を出力する代わりに、の範囲で一意に定まる、以上の自然数を出力してください。

最後に改行してください。

2
1 2

2

・です。より,となります。

5
1 2
2 3
5 4
2 4

399297744

・です。より,となります。

20
1 10
2 8
14 12
4 15
17 18
20 6
16 1
3 5
6 8
11 3
6 12
19 4
17 13
7 10
10 13
4 6
9 6
4 1
3 8

220664546

・です。より,となります。