图 $G = (V, E)$ 的一个匹配是指其边集的一个子集 $M$，使得 $M$ 中任意两条边都没有公共端点。

对于图 $G$ 中的无序顶点对 $(u, v)$（其中 $u \neq v$ 且 $(u, v) \notin E$），如果向 $G$ 中添加边 $(u, v)$ 后，图 $G$ 的最大匹配大小增加，则称该顶点对为“有前途的”。

给定一个包含 $n$ 个顶点和 $n - 1$ 条边的连通图 $G$。请找出图 $G$ 中有前途的顶点对的数量。

输入格式

输入的第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示图 $G$ 的顶点数。接下来的 $n - 1$ 行描述了图 $G$ 的边。其中第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n$)，表示第 $i$ 条边连接顶点 $a_i$ 和 $b_i$。图 $G$ 的顶点编号为 $1$ 到 $n$。

输出格式

输出一行一个整数，表示图 $G$ 中有前途的顶点对的数量。

样例

输入 1

6
1 2
1 3
1 4
1 5
2 6

输出 1

3

说明

样例的解释：唯一的有前途的顶点对是 $(3, 4)$，$(3, 5)$ 和 $(4, 5)$。