安装在摩拉维亚废弃矮人矿井中的全自动微型啤酒厂，确实是矮人工程学独创性和工艺的证明！然而，地震有时会震动矿井，导致管道和漏斗错位，将珍贵的液体洒在地板上。作为酿酒厂安全部门的尊贵主管，在发生地震时，你有责任关闭每个大厅里的机器。

穿过隧道需要时间，因此你不可避免地会迟到许多机器处。这是无法避免的，但你希望尽量减少洒出的液体总量。

矮人矿井由 $n$ 个大厅和连接它们的 $n-1$ 条隧道组成。整个系统是连通的，因此可以从任何一个大厅到达其他任何大厅。穿过一条隧道需要 1 个单位时间。关闭机器和穿过大厅不需要时间。在每个大厅中，在地震发生后时间 $t$ 关闭机器会洒出 $t$ 升液体。地震只有一次，地震同时影响所有大厅，并且你不能在地震发生前关闭任何机器。你可以从任何一个大厅开始。

Goodluck Mine, Passage by Ashley Dace. License CC BY-SA 2.0.

样例

在样例输入 1 中，矿井看起来像这样：

1 2 3

如果你从 2 号大厅开始，并按 2, 1, 2, 3 的顺序访问其余大厅，那么你可以在时间 0（在 2 号大厅）、时间 1（在 1 号大厅）和时间 3（在 3 号大厅）关闭它们的机器。这总共浪费了 $0 + 1 + 3 = 4$ 升液体。如果改为从 1 号大厅开始，并按 1, 2, 3 的顺序访问大厅，则浪费的液体总量为 $0 + 1 + 2 = 3$ 升，这更好。

输入格式

第一行包含一个整数 $n$，表示大厅的数量。我们假设大厅编号为 $1, \dots, n$。接下来的 $n-1$ 行，每行包含两个空格分隔的整数 $u$ 和 $v$，其中 $1 \le u < v \le n$，表示大厅 $u$ 和大厅 $v$ 之间有一条隧道。

输出格式

输出一个整数：最少洒出的液体量（以升为单位）。

数据范围

我们始终有 $1 \le n \le 10^5$。

你的解决方案将在若干测试组上进行测试，每组测试都有一定的分数。每个测试组包含一组测试用例。要获得一个测试组的分数，你需要解决该组中的所有测试用例。你的最终得分将是单次提交的最高得分。

样例输入 1

3
1 2
2 3

样例输出 1

3

样例输入 2

4
1 2
1 3
1 4

样例输出 2

7

样例输入 3

1

样例输出 3

0