J. 上学
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

usst 小学里有 $$$n$$$ 名学生,他们分别居住在 $$$n$$$ 个地点,第 $$$i$$$ 名学生居住在第 $$$i$$$ 个地点,这些地点由 $$$n - 1$$$ 条双向道路连接,保证任意两个地点之间可以通过若干条双向道路抵达。学校则位于另外的第 $$$0$$$ 个地点,第 $$$0$$$ 个地点与第 $$$1$$$ 个地点之间有另外一条双向道路链接。

最近学校开始启用校车来接学生上学,每一辆校车上都可以坐无限个学生,且每辆校车在一天内不会重复经过一条道路,校车终点始终为学校。每一位学生一天内只能乘坐一辆校车,且只能在自己居住的节点处上车,在学校下车。为了节省资金,学校会在保证每位学生都能坐上校车的前提下,安排最少数量的校车,每天早上从某些地点出发,并经过若干道路和地点最终抵达学校。第 $$$x$$$ 位学生可以自由选择一辆经过第 $$$x$$$ 个地点的校车,搭乘它到达学校。

现在学校想要从 $$$n$$$ 个学生中选出 $$$3$$$ 人参加某个比赛,但是学校不希望这 $$$3$$$ 人之间太过 "熟悉",请问一共有多少种不同的选人方案。

如果一种选择方案中, $$$3$$$ 个人可能在同一天里都乘坐上同一辆校车,那就称这 $$$3$$$ 个人之间太过 "熟悉"。

对于任意两个方案,如果存在一名学生在一个方案中且不在另一个方案中,那么就认为这两种方案不同。

Input

输入第 $$$1$$$ 行包含 $$$1$$$ 个正整数 $$$n$$$ ,代表学生数量和学生居住的地点数量。($$$3 \leq n \leq 2\times 10^5$$$)

接下来 $$$n - 1$$$ 行每行有 $$$2$$$ 个正整数 $$$u, v$$$ ,代表第 $$$u$$$ 个地点与第 $$$v$$$ 个地点之间有一条双向道路。($$$1 \leq u, v \leq n$$$)

Output

输出一行,一个整数,代表选人方案数量。

Examples
Input
5
1 2
2 3
3 4
4 5
Output
0
Input
5
1 2
2 3
2 4
1 5
Output
8
Note

对于第二组样例,校车会从第 $$$3,4,5$$$ 个地点出发,前往学校。合法的选人方案有 {$$$1, 2, 5$$$}, {$$$1, 3, 4$$$}, {$$$1, 3, 5$$$}, {$$$1, 4, 5$$$}, {$$$2, 3, 4$$$}, {$$$2, 3, 5$$$}, {$$$2, 4, 5$$$}, {$$$3, 4, 5$$$}