题目描述

给定一棵$n$个节点的树，节点编号为$1$~$n$，初始时每个节点都未被占领。$Alice$和$Bob$在上面玩游戏，两个人轮流操作（$Alice$先手），每人每步操作会占领一个未被占领的节点，直到所有节点都被占领为止。

定义树上两点的距离为它们之间最短路径的边数，所有操作结束后，游戏的分值为$Alice$占领的所有节点两两间的最大距离。$Alice$希望这个分值尽可能小，而$Bob$希望这个分值尽可能大。如果两人都采取最优策略行动，请问游戏的最终分值是多少。

输入格式

第一行包含一个正整数$n$。

接下来$n-1$行，每行两个正整数$x$,$y$，表示树上的一条边。

输出格式

输出一行一个整数，表示答案。

样例输入

3
1 2
1 3

样例输出

1

数据范围

本题采用子任务评测。

对于所有数据，$3\leq n\leq 100000,1\leq x,y\leq n$

$subtask 1:25pts$ $n\leq 10$

$subtask 2:25pts$ 保证答案 $\geq$ 直径长度$-1$

$subatsk 3:50pts$ 无特殊限制