markdown

E. 谢尔盖与地铁

谢尔盖·谢苗诺维奇是某县城 N 的市长，他过去常常日夜思考如何进一步改善 N 城居民的生活。不幸的是，对他来说，所有能做的事情都已经做完了，白天他再也想不出什么可以改进的地方了（他现在更喜欢晚上睡觉）。然而，他的助手们找到了一个办法：他们在一张纸上画了一个虚构的城市，并建议市长可以对这个城市提出改进方案。

现在，他有一张虚构城市的地图，上面有 $n$ 个地铁站。某些站点之间由隧道直接相连，且整个地图构成一棵树（助手们当时时间紧迫，热情也不高）。这意味着每对站点之间恰好存在一条简单路径。我们称一条路径是简单的，如果它每条隧道最多经过一次。

谢尔盖·谢苗诺维奇最喜欢的一个质量指标是所有站点对之间距离的总和。两个站点之间的距离是指它们之间路径上所需经过的最少隧道数量。

谢尔盖·谢苗诺维奇决定在地铁图中添加新的隧道。具体来说，他会连接任意两个原本没有直接隧道相连、但存在一个共同邻居的站点 $u$ 和 $v$，即存在一个站点 $w$，使得原始地图中 $u$ 与 $w$ 之间有隧道，且 $w$ 与 $v$ 之间有隧道。你的任务是计算在新地图中，所有站点对之间距离的总和。

输入

第一行包含一个整数 $n$（$1 \le n \le 200000$）——市长助手所画虚构城市中的地铁站数量。
接下来的 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$），表示编号为这两个值的站点之间有一条直接隧道。

保证这 $n$ 个站点和 $n-1$ 条隧道构成一棵树。

输出

输出一个整数，表示在谢尔盖·谢苗诺维奇将所有在原始地图中拥有共同邻居的站点对之间都添加新隧道之后，所有站点对之间距离的总和。

样例

输入样例 1

4
1 2
1 3
1 4

输出样例 1

6

输入样例 2

4
1 2
2 3
3 4

输出样例 2

7

注释

在第一个样例中，新地图中所有站点对之间都有直接连接，因此距离总和为 $6$。

在第二个样例中，新地图中除了站点对 $(1,4)$ 之外，所有站点对之间都有直接隧道。这两个站点之间的距离为 $2$。