谢尔盖·谢苗诺维奇(Sergey Semyonovich)是N县市的市长,他曾经日日夜夜地思考如何进一步改善Nkers的生活。对他来说不幸的是,一切都已经完成了,白天他无法再想到任何可能的改进(他现在更喜欢晚上睡觉)。然而,他的助手们找到了解决方案,他们现在在纸上画了一个想象中的城市,并建议市长提出改进建议。
现在他有一张想象中的城市地图,上面有 $$$n$$$ 地铁站。有些车站直接与隧道相连,整个地图就是一棵树(助手时间不够,热情不够)。这意味着每对站之间恰好存在一条简单路径。如果一条路径使用每个隧道不超过一次,我们称该路径为简单路径。
Sergey Semyonovich 最喜欢的质量目标之一是每对站点之间所有成对距离的总和。两个站点之间的距离是它们之间的路径上可能存在的最小隧道数。
Sergey Semyonovich 决定在地铁地图上添加新隧道。特别是,他连接了任意两个没有直接隧道连接但共享公共邻居的站$$$u$$$和$$$v$$$,即存在这样一个站$$$w$$$,原始地图在$$$u$$$和$$$w$$$之间有一条隧道,在$$$w$$$和$$$v$$$之间有一条隧道。您的任务是计算新地图中所有站对之间的成对距离总和。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 200\,000$$$) - 由市长助理绘制的假想城市中的地铁站数量。以下每条 $$$n - 1$$$ 行都包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$),这意味着具有这些索引的车站与直接隧道相连。
保证这些$$$n$$$站和$$$n - 1$$$隧道形成一棵树。
输出
在 Sergey Semyonovich 在原始地图中共享公共邻居的所有车站对之间绘制新隧道后,打印一个整数,该整数等于所有车站对之间的距离之和。
示例
输入 #1
4 1 2 1 3 1 4
输出 #1
6
输入 #2
4 1 2 2 3 3 4
输出 #2
7
注意
在第一个示例中,在新地图中,所有站对共享直接连接,因此距离总和为 $$$6$$$。
在第二个示例中,新地图在除 $$$(1, 4)$$$ 之外的所有车站对之间都有一条直接隧道。对于这两个站,距离为 $$$2$$$。