题目描述

$Mahmoud$ 和 $Ehab$ 继续他们的冒险！恶魔大陆的每个人都知道，$Evil$ 博士喜欢二分图，尤其是树。

树是一个连通的无环图。二分图是一个图，它的顶点可以划分为 $2$ 个集合，对于图中的每条边 $(u,v)$，$u$ 和 $v$ 属于不同的集合。

$Evil$ 博士给了 $Mahmoud$ 和 $Ehab$ 一棵由 $n$ 个节点组成的树，并要求他们向其中添加边，使图仍然是二分图。 添加这些边后，该图应该还是简单图（不包含自回环和重边）。请问他们可以添加的最大边数是多少？

自回环是一条起点和终点相同的边。重边是指两个顶点之间存在超过一条边的情况。要注意自回环和回路是不一样的。

输入格式

输入的第一行包含一个整数 $n$，表示树中的节点数 $(1 \le n \le 10^5)$。

接下来的 $n-1$ 行包含整数 $u$ 和 $v$ $(1 \le u, v \le n$，$u ≠ v)$，表示树上边的描述。保证给定的图是一棵树。

输出格式

输出一个整数，表示 $Mahmoud$ 和 $Ehab$ 在满足条件时可以添加到树中的最大边数。

3
1 2
1 3

0

唯一可以添加的边是 $(2,3)$，但添加此边将使该图不满足二分图，所以答案是 $0$。

5
1 2
2 3
3 4
4 5

2

可以添加边 $(1,4)$ 和 $(2,5)$。