题目描述

给定一棵 \(n\) 个点的树，对于每一次操作，你可以选定三个点 \(x,y,z\) ，要求 \(x\) 与 \(y\) 相邻， \(y\) 与 \(z\) 相邻，然后将所有与 \(x\) 相邻的节点和 \(z\) 连边并断掉与 \(x\) 的连边，最后将 \(x\) 和 \(z\) 连边。

你需要进行最少次数的操作（可能为 \(0\)），使得这个图最终成为一个菊花图（\(n-1\) 个点都和同一个点连边）。

输入格式

第一行一个整数 \(n\) 。

接下来 \(n-1\) 行表示一棵树。

输出格式

一行一个整数表示最少操作次数，保证答案不超过 \(10^{18}\) 。

样例

样例输入 1

6
4 5
2 6
3 2
1 2
2 4

样例输出 1

1

样例输入 2

4
2 4
4 1
3 4

样例输出 2

0

提示说明

对于 \(100\%\) 的数据

\(3 \le n\le 2 \times 10^5\)