题目描述

给定一棵大小为 $n$ 的树，树上每条边的长度均为 $1$。

很明显，树上任意两点间存在一条简单路径，路径的长度即为边的数量。

本题中，我们不考虑起点和终点是同一个点的路径（即不考虑长度为 $0$ 的路径）；同时，以节点 $u$ 为起点节点 $v$ 为终点的路径，与以节点 $v$ 为起点节点 $u$ 为终点的路径视为同一条。

求：图中存在多少条长度为偶数的路径？

输入格式

第一行，一个整数 $n(2 \le n \le 2 \times 10^5)$。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u,v \le n, u \neq v$），表示树上一条边连接的两个节点的编号。

数据保证这是一棵树。

输出格式

输出一个整数，表示图中存在多少条长度为偶数的路径。

样例

6
1 2
1 3
2 4
2 5
3 6

7

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n \le 20$
• 对于 $60\%$ 的数据，$n \le 2000$
• 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$