A15586 | 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?

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).

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