Migrated from Lutece 2860 道路修建

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在漫长的战争后，整个大陆迎来了和平。在签订和平条约后，莱顿沙夫特里希也开始开展基础设施修建工程，首先要修建的就是路网。

莱顿沙夫特里希国有 $n$ 个城市，编号为 $1$ 到 $n$，其中编号为 $1$ 的城市是首都莱登。因为常年战争，目前路网只保留了主干部分，能够使得各城市连通，总的来说，目前有 $n-1$ 条双向连接两城市的道路，使得任意两城市都能互相到达。

近期，莱顿沙夫特里希国决定修建战后的第一条道路，这条道路会连接首都与另外一个非首都城市，以作为纪念并补充路网满足国民需要。C·H 邮政公司也希望这条道路能使邮件投递更快，所以会参与投资这一项目，以提出自己的意见。

公司希望建好这条路后，首都到各个城市的最短距离的平均值最小，也就是首都到各个城市的最短距离的和最小。你需要告诉 C·H 邮政公司的社长，当建好这条路后，首都到各个城市的最短距离的和最小会是多少。这里定义两城市之间的距离为从一个城市到另一个城市所要经过的道路条数。

Input

第一行一个整数 $n\ (1\le n\le 10^5)$，表示莱顿沙夫特里希国的城市数。

接下来 $n-1$ 行，每行两个整数 $u,v\ (1\le u,v\le n, u\neq v)$，表示编号为 $u,v$ 的两个城市之间有一条道路双向直接相连。保证任意两城市都能互相到达。

Output

输出一行一个整数，表示首都到各个城市的最短距离的和的最小值。

Samples

6
1 2
2 3
3 4
3 5
3 6

8

Note

选择 $3$ 号城市，此时首都到各个城市的最短距离的和为：

$$d(1,1) + d(1, 2) + d(1, 3) + d(1, 4) + d(1, 5) + d(1, 6) = 0 + 1 + 1 + 2 + 2 + 2 = 8 $$

其中，$d(x,y)$ 表示编号为 $x$ 的城市到编号为 $y$ 的城市的最短距离。

可以证明，这个最短距离和是最小的，因此输出 $8$。

Resources

The 19th UESTC Programming Contest Preliminary