← 返回题目列表

Codeforces · 1776/M

M. 帕尔马干酪配海鲜

中文机器翻译题面 查看原题

“Parmigiana di melanzane”是一道典型的意大利菜。亚历山德罗(Alessandro)和比安卡(Bianca)的口味截然不同:亚历山德罗(Alessandro)喜欢将帕尔马干酪(Parmigiana)与海鲜一起吃,但比安卡(Bianca)认为这是一种暴行!为了决定他们准备的菜肴中包含哪些成分,他们玩以下游戏。

有 $$$n$$$ 可能的成分,标记为 $$$1$$$ 到 $$$n$$$。标签越高,成分越接近海鲜。这些成分通过 $$$n - 1$$$ 边连接,从而形成一棵树。亚历山德罗和比安卡轮流,亚历山德罗先走。他们交替选择一种终端成分 $$$x$$$,即当前与最多一种其他成分相连的成分,并将其从树中删除。如果最终成分 $$$x$$$ 是 Alessandro 选择的,它就会出现在食谱中;如果比安卡选择了它,则将其丢弃。

帕尔马干酪的味道以配方中成分的最大标签来衡量。亚历山德罗想要最大化味道,而比安卡想要最小化味道。如果两者发挥最佳效果,帕尔马干酪的味道如何?

输入

第一行包含一个整数 $$$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$$$ 条边连接的成分。

保证边形成一棵树(即,任何一对成分都通过边连接,可能是间接的)。

输出

如果 Alessandro 和 Bianca 都发挥最佳,则打印品味值。

示例

输入 #1

4
1 2
1 3
1 4

输出 #1

4

输入 #2

5
1 5
5 3
3 4
4 2

输出 #2

3

注意

在第一个样本中,Alessandro 在第一回合可以选择终端成分 $$$4$$$。该成分已添加到配方中。由于 $$$4$$$ 是成分的最大标签,因此无论后面的选择如何,味道都是 $$$4$$$。

在第二个示例中,Bianca 可以确保配方中既不包含 $$$4$$$ 也不包含 $$$5$$$ 成分,在这种情况下,Alessandro 可以包含 $$$3$$$。因此,味道是$$$3$$$。