题目描述

有一个有 $N$ 个点的树。树的节点从 $1$ 到 $N$ 编号。第 $i$ 条边连接点 $A_i$ 和点 $B_i$。

求满足下列条件的整数三元组 $(i, j, k)$ 的数量：

• $1 \leq i < j < k \leq N$；
• 树上没有一条简单路径包含 $i$，$j$，$k$ 三点。

限制

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, B_i \leq N$

输入格式

$N$

$A_1$ $B_1$

$A_2$ $B_2$

$\vdots$

$A_{N-1}$ $B_{N-1}$

输出格式

输入答案。

样例

5
1 2
2 3
2 4
1 5

2

6
1 2
2 3
3 4
4 5
5 6

0

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

91