题目描述

Cherry 和 Chocolate 在一棵树上进行游戏。首先，Cherry 选择一个节点并将其涂成粉色。然后，Chocolate 选择另一个节点并将其涂成棕色。之后，Cherry 再选择另一个节点并将其涂成粉色。游戏到此结束，Chocolate 没有第二次行动的机会。

对于每个节点 $v$，如果从 $v$ 到棕色节点的所有路径都至少经过一个粉色节点，则 Cherry 获得一分。

Cherry 希望最大化自己的得分，而 Chocolate 则希望最小化她的得分。如果双方都采取最优策略，Cherry 的得分会是多少？

输入格式

第一行包含一个整数 $n$（$3 \le n \le 10^5$），表示树的节点数。

接下来的 $n - 1$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i, b_i \le n$），表示节点 $a_i$ 与 $b_i$ 之间有一条边。

输出格式

输出一个整数，表示在双方均采取最优策略时 Cherry 的得分。

4
1 2
2 3
2 4

3

提示

翻译由 DeepSeek V4 Pro 完成