珅泽教育所在地区有 $N$ 座城市，编号为 $1$ 到 $N$。城市之间有 $N-1$ 条双向道路，任意两座城市之间都能互相到达，并且每条道路的长度都为 $1$，因此这些城市和道路构成一棵树。

对于两座不同的城市 $u$ 和 $v$，用 $dist(u,v)$ 表示从 $u$ 到 $v$ 的最短路径所经过的道路数量。刘老师希望知道所有无序城市对之间的距离总和，也就是

请计算并输出这个总和。

输入格式

第一行输入一个整数 $N$，表示城市数量。

接下来 $N-1$ 行，每行输入两个整数 $a_i$ 和 $b_i$，表示城市 $a_i$ 与城市 $b_i$ 之间有一条双向道路。

输出格式

输出一个整数，表示所有无序城市对之间的距离总和。

5
1 5
2 1
4 3
3 2

20

7
4 7
1 4
3 1
5 6
1 2
4 5

46

9
6 5
3 7
3 1
1 4
5 3
7 8
8 9
1 2

96

数据范围与约定

• $2\le N\le10^5$
• 输入图是一棵树