Mahmoud 和 Ehab 继续他们的冒险!邪恶之地的每个人都知道,邪恶博士喜欢二分图,尤其是树。
树是一个连通的非循环图。二分图是一种图,其顶点可以划分为 2 个集合,对于属于该图的每条边 (u, v),u 和 v 属于不同的集合。您可以在下面的注释部分找到树和二分图的更正式的定义。
Evil 博士给了 Mahmoud 和 Ehab 一棵由 n 个节点组成的树,并要求他们以这样的方式向其添加边,使图仍然是二分图。此外,添加这些边后,图形应该很简单(不包含循环或多个边)。他们最多可以添加多少条边?
环是一条边,它将节点与其自身连接起来。当每对节点之间不超过一条边时,图不包含多条边。循环和循环并不相同。
输入
输入的第一行包含一个整数 n — 树中的节点数 (1 ≤ n ≤ 105)。
接下来的 n - 1 行包含整数 u 和 v (1 ≤ u, v ≤ n, u ≠ v) - 树边的描述。
保证给定的图是一棵树。
输出
输出一个整数——Mahmoud 和 Ehab 在满足条件的情况下可以添加到树中的最大边数。
示例
输入 #1
3 1 2 1 3
输出 #1
0
输入 #2
5 1 2 2 3 3 4 4 5
输出 #2
2
注意
树定义:https://en.wikipedia.org/wiki/Tree_(graph_theory)
二分图定义:https://en.wikipedia.org/wiki/Bipartite_graph
在第一个测试用例中,可以以这种方式添加的唯一边(该图不包含循环或多条边)是 (2, 3),但添加此边将使图成为非二分图,因此答案为 0。
在第二个测试用例中,Mahmoud 和 Ehab 可以添加边 (1, 4) 和 (2, 5)。