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 的得分。

样例

样例输入 1

4
1 2
2 3
2 4

样例输出 1

3