問題文

N 頂点の木が与えられます。木の頂点にはそれぞれ 1 から N までの番号が振られています。
i 番目の辺は、頂点 a_i と頂点 b_i を双方向に結んでおり、長さは全て 1 です。

• {\displaystyle\sum_{u = 1}^{N - 1} \sum_{v = u + 1}^{N} \operatorname{dist}(u, v)}

の値を求めてください。

ただし、\operatorname{dist}(u,v) は、頂点 u から 頂点 v までの最短距離とします。

制約

• 2 \leq N \leq 100000
• 1 \leq a_i, b_i \leq N
• 与えられるグラフは木である
• 入力は全て整数で与えられる

入力例 1

2
1 2

出力例 1

1

\operatorname{dist}(1, 2) = 1 であるので、答えは 1 です。

入力例 2

4
1 2
1 3
1 4

出力例 2

9

• \operatorname{dist}(1, 2) = 1
• \operatorname{dist}(1, 3) = 1
• \operatorname{dist}(1, 4) = 1
• \operatorname{dist}(2, 3) = 2
• \operatorname{dist}(2, 4) = 2
• \operatorname{dist}(3, 4) = 2

であるので、これらを足し合わせた 9 が答えになります。　

入力例 3

12
1 2
3 1
4 2
2 5
3 6
3 7
8 4
4 9
10 5
11 7
7 12

出力例 3

211