题目描述

Mahmoud 和 Ehab 的冒险仍在继续！众所周知，在邪恶之地，Dr. Evil 喜欢二分图，尤其喜欢树。

一棵树是一个连通且无环的图。二分图是指可以将所有顶点划分为 $2$ 个集合，使得对于每条属于该图的边 $(u,v)$，$u$ 和 $v$ 属于不同的集合。更形式化的树和二分图定义可见下文注释部分。

Dr. Evil 给了 Mahmoud 和 Ehab 一棵包含 $n$ 个节点的树，并要求他们往这棵树中添加若干条边，使得添加完之后，图依然保持为二分图。此外，添加边后图需要保持简单（即图中不能有自环或重边）。你能求出他们最多可以添加多少条边吗？

自环是指一条边的两个端点是同一个节点。简单图要求对于每一对节点，最多只有一个边连接它们。环和自环是不同的概念。

输入格式

输入的第一行为一个整数 $n$，表示树的节点数（$1\leq n\leq 10^{5}$）。

接下来的 $n-1$ 行，每行为两个整数 $u$ 和 $v$（$1\leq u,v\leq n$，$u\neq v$），描述树中的一条边。

保证给定的图是一棵树。

输出格式

输出一个整数，表示在满足条件的情况下，最多可以往树中添加多少条边。

3
1 2
1 3

0

5
1 2
2 3
3 4
4 5

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)$。