CF1776M.Parmigiana With Seafood

The "Parmigiana di melanzane" is a typical Italian dish. Alessandro and Bianca have very different tastes when it comes to it: Alessandro loves to eat Parmigiana with seafood, but Bianca thinks it is an atrocity! To decide which ingredients to include in the dish they prepare, they play the following game.

There are $n$ possible ingredients, labeled from $1$ to $n$. The higher the label, the closer the ingredient is to being seafood. The ingredients are connected by $n - 1$ edges, in such a way as to form a tree. Alessandro and Bianca take turns, with Alessandro going first. They alternately choose a terminal ingredient $x$, that is an ingredient currently connected to at most one other ingredient, and remove it from the tree. If the terminal ingredient $x$ was chosen by Alessandro, it goes in the recipe; if it was chosen by Bianca, it is discarded.

The taste of the Parmigiana is measured as the maximum label of an ingredient in the recipe. Alessandro wants to maximize the taste, while Bianca wants to minimize the taste. If both play optimally, what is the taste of the Parmigiana?

“帕尔马干酪茄子”是一道经典的意大利菜肴。亚历山德罗和比安卡对这道菜的口味偏好截然不同：亚历山德罗非常喜欢在帕尔马干酪茄子中加入海鲜，而比安卡则认为这是种亵渎！为了决定他们所准备的这道菜中应包含哪些食材，两人玩起了如下游戏。

共有 $n$ 种可能的食材，编号为 $1$ 到 $n$。编号越大，该食材越接近海鲜。这些食材通过 $n - 1$ 条边相互连接，构成一棵树。亚历山德罗和比安卡轮流进行操作，亚历山德罗先行。两人轮流选择一个叶节点食材 $x$（即当前至多只与另一食材相连的食材），并将其从树中移除。若该叶节点食材 $x$ 由亚历山德罗选出，则它被加入食谱；若由比安卡选出，则它被丢弃。

帕尔马干酪茄子的“美味度”定义为食谱中所有食材编号的最大值。亚历山德罗希望最大化美味度，而比安卡则希望最小化美味度。若双方均以最优策略进行游戏，则最终帕尔马干酪茄子的美味度是多少？

The first line contains an integer $n$ ($2\le n \le 100\,000$) — the number of ingredients.

Each of the following $n-1$ lines contain two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le n$, $u_i \ne v_i$) — the ingredients that the $i$-th edge connects.

It is guaranteed that the edges form a tree (i.e., any pair of ingredients is connected by the edges, possibly indirectly).

第一行包含一个整数 $n$（$2\le n \le 100\,000$）—— 食材的数量。

接下来的 $n-1$ 行中，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，且 $u_i \ne v_i$）—— 表示第 $i$ 条边所连接的两种食材。

保证这些边构成一棵树（即任意两种食材之间都可通过边（可能间接）相连）。

Print the value of the taste if both Alessandro and Bianca play optimally.

如果亚历山德罗和比安卡都采取最优策略，输出“口味值”的数值。

In the first sample, Alessandro can choose terminal ingredient $4$ in the first turn. This ingredient is added to the recipe. Since $4$ is the maximum label of an ingredient, the taste is $4$ regardless of the choices that follow.

In the second sample, Bianca can make sure that neither ingredient $4$ nor $5$ are included in the recipe, in which case Alessandro can include $3$. Thus, the taste is $3$.

在第一个样例中，亚历山德罗可以在第一轮选择终端原料 $4$。该原料将被加入食谱中。由于 $4$ 是所有原料编号中的最大值，因此无论后续如何选择，最终的风味值均为 $4$。

在第二个样例中，比安卡可以确保原料 $4$ 和 $5$ 均不被加入食谱，此时亚历山德最多只能加入原料 $3$。因此，最终的风味值为 $3$。