【题目描述】

一棵树有n个结点，编号为1~n。

定义Tree[L,R]表示为了使得L~R号点两两连通，最少需要选择的边的数量。

求：$\sum\limits_{L=1}^{n} \sum\limits_{R=L}^{n} Tree[L,R]$

【输入格式】

第一行一个数，n表示点数

接下来n-1行，每行两个数，x和y，表示一条连接x号点和y号点的边

【输出格式】

输出一个数表示答案

【输入输出样例】

输入

4
1 4 
1 3 
2 4 

输出

16 

【数据范围】

对于20%的数据：n<=10

对于40%的数据：n<=300

对于60%的数据：n<=3000

对于另外20%的数据：树呈一条链

对于100%的数据：n<=100000，1<=x,y<=n