题目内容

小塔有一颗$n$个点的树。如果树上存在一个点$w$，使得原始的树上存在边$(u,w)$和$(w,v)$，那么我们可以添加一条边$(u,v)$.

小塔想知道，添加若干条边之后，树上任意两点之间的距离之和最少是多少。即求$\sum_{i=1}^{n}\sum_{j=1}^{n}dist(i,j)$ 。

输入描述

第一行输入一个整数$n(2≤n≤2✖10^5)$代表树上的点数。

此后$n-1$行，第$i$行输入两个整数$u_i$和 $u_i(1≤u_i,v_i≤n；u_i≠v_i)$表示树上第$i$条 $u_i和v_i$。保证树联通，没有重边。

输出描述

在一行输出一个整数，代表树上 距离之和的最小值

样例1

输入

5
1 2
1 3
2 4
2 5

输出

24

**说明 **

可以添加边为（1,4),(1,5),(2,3),(4,5) 加边之后，1号点到其他点的距离为[0,1,1]

2号点到其他点的距离为[1,0,1,1,1]

3号点到其他点的距离为

4号点到其他点的距离为

5号点到其他点的距离为

距离总和为24

样例2

输入

输出