KOI 公园的草坪上有一个许多蚂蚁共同生活的蚁巢。蚁巢由 $N$ 个房间组成，有 $N-1$ 条通道直接连接不同房间，任意两个不同房间之间都可以经过通道到达。也就是说，蚁巢是一棵有 $N$ 个顶点的树。每个房间的编号为 $1$ 至 $N$。

蚁巢的每个房间最多能住一只蚂蚁。如果两只蚂蚁所在的房间被通道直接连接，它们就会彼此感到不舒服。因此，目前每条通道连接的两个房间中，最多只有一个住着蚂蚁。

蚂蚁们很聪明，因此在满足这一条件的前提下，目前蚁巢中居住的蚂蚁数量已经尽可能多。换言之，如果再来一只蚂蚁，那么无论怎样安排所有蚂蚁的房间，都无法满足上述条件。

在一个晴朗的夏日，许多人来到 KOI 公园野餐。人们在草坪上野餐时，构成蚁巢的土壤会崩塌，从而恰好新增一条连接两个不同房间的通道。这两个房间原先也可能已有通道直接连接。换言之，对于任意两个整数 $1 \le i < j \le N$，都可能新增一条连接房间 $i$ 和房间 $j$ 的通道，无论此前是否已有连接它们的通道。

新增通道可能直接连接两只蚂蚁居住的房间，使这对蚂蚁感到不舒服。因此，目前住在蚁巢里的蚂蚁可能需要重新安排位置，以满足条件。根据 $(i,j)$ 的选择，有时可以做到，但有时无论现有蚂蚁怎样重新安排，都无法满足条件。这种情况下，可能必须赶走一些原先的居民。

对于两个整数 $1 \le i < j \le N$，如果新增连接房间 $i$ 和房间 $j$ 的通道后，蚂蚁们不赶走任何同伴，仅通过适当调整位置就能满足条件，则称 $(i,j)$ 为和平对。给定蚁巢结构，请计算和平对的数量。

数据范围

• $2 \le N \le 250\,000$
• $u \ne v$, $1 \le u,v \le N$
• 给定的蚁巢具有树结构。

子任务

1. (8 分) $N \le 16$.
2. (6 分) $N \le 80$.
3. (18 分) $N \le 400$.
4. (18 分) $N \le 2000$.
5. (6 分) $N \le 10000$.
6. (8 分) $N \le 50000$.
7. (36 分) 无额外限制。

输入格式

第一行给出 $N$。

接下来的 $N-1$ 行，每行给出一条通道连接的两个房间的编号 $u$ 和 $v$。

输出格式

第一行输出和平对的数量。

样例

输入格式 1

4
1 2
1 3
1 4

输出格式 1

3

说明

最初最多可以住 3 只蚂蚁，达到这一数量的唯一安排是 $\{2,3,4\}$。在原先已直接连接的房间之间新增通道，不需要调整位置，这样的情况共有 3 种。其余情况下，无论怎样新增通道，都不存在可容纳 3 只蚂蚁的安排。

输入格式 2

6
1 2
2 3
3 4
4 5
5 6

输出格式 2

15

说明

最初最多可以住 3 只蚂蚁，其中一种可行的安排是 $\{1,3,6\}$。无论新增怎样的通道，都存在可容纳 3 只蚂蚁的安排。

输入格式 3

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

输出格式 3

11