#agc009d. [agc009_d]Uninity

[agc009_d]Uninity

题目描述

我们递归地定义树的“统一性”如下:(“Uni”是日语中海胆的意思。)

  • 仅包含一个顶点的树的统一性为 00
  • 假设有 kk 个统一性为 kk 的树以及一个顶点 vv。如果从每棵树中选择一个顶点并用边连接到 vv,则得到的树的统一性为 k+1k+1

可以证明,统一性为 kk 的树也是统一性为 k+1,k+2,k+1, k+2, \ldots 的树,依此类推。

给定一棵由 NN 个顶点组成的树。树的顶点编号为 11NN,第 ii 条边连接顶点 aia_ibib_i

找出使得给定的树具有统一性 kk 的最小值。

约束条件

  • 2N1052 ≤ N ≤ 10^5
  • 1ai,biN(1iN1)1 ≤ a_i, b_i ≤ N(1 ≤ i ≤ N-1)
  • 给定的图是一棵树。

输入

输入以以下格式从标准输入给出:

NN a1a_1 b1b_1 : aN1a_{N-1} bN1b_{N-1}

输出

打印使得给定的树具有统一性 kk 的最小值。

示例 1

7
1 2
2 3
2 4
4 6
6 7
7 5

输出 1

可以通过以下方式构造包含顶点 11223344 的统一性为 11 的树:顶点 11 构成的统一性为 00 的树,顶点 33 构成的统一性为 00 的树,顶点 44 构成的统一性为 00 的树和顶点 22

可以通过以下方式构造包含顶点 5577 的统一性为 11 的树:顶点 55 构成的统一性为 11 的树和顶点 77

可以通过以下方式构造包含顶点 11223344556677 的统一性为 22 的树:顶点 11223344 构成的统一性为 11 的树,顶点 5577 构成的统一性为 11 的树以及顶点 66

示例 2

12
1 2
2 3
2 4
4 5
5 6
6 7
7 8
5 9
9 10
10 11
11 12

输出 2