Type: Default 2000ms 256MiB

树上的路灯很社恐

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

有一棵 nn 个点的树,点编号为 11 到 nn。

树上每个点都有一盏路灯。两盏路灯之间的社交距离定义为它们所在点之间简单路径的边数。

现在,路灯们只愿意和距离为偶数的路灯组成"夜间摸鱼小组"。请问有多少对不同的路灯 (u,v)(u,v) 满足 u<vu<v 且 uu 与 vv 的距离为偶数?

Format

Input

第一行一个整数 n(2≤n≤2×105)n(2 \le n \le 2 \times 10^5)。

接下来 n−1n-1 行,每行两个整数 u,v(1≤u,v≤n)u,v(1 \le u,v \le n),表示树上有一条连接 uu 和 vv 的边。

输入保证给出的是一棵树。

Output

输出一行一个整数,表示距离为偶数的点对数量。

Samples

5
1 2
1 3
3 4
3 5
4

Note

样例说明:

以 11 为根时,深度为偶数的点有 1,4,51,4,5,深度为奇数的点有 2,32,3。

距离为偶数的点对为:(1,4),(1,5),(4,5),(2,3)(1,4),(1,5),(4,5),(2,3)共 44 对。