分数: 1400 点
问题陈述
我们将递归地定义 团结 一棵树,如下:(大学 是日语中海胆的意思。)
- 由一个顶点组成的树是一棵树 0.
- 假设有零个或多个无穷大树 k,和一个顶点 v。如果从每棵无穷大树中选择一个顶点 k 并连接到 v 有一条边,生成的树是一棵统一树 k+1.
可以证明,一棵统一树 k 也是一棵团结之树 k+1,k+2,...等等。
给你一棵树,其中包含 N 顶点。 树的顶点已编号 1 通过 N,以及 i- 第 N-1 边连接顶点 a_i 和 b_i.
求最小值 k 使得给定的树是一棵统一树 k.
约束
- 2 ≦ N ≦ 10^5
- 1 ≦ a_i, b_i ≦ N(1 ≦ i ≦ N-1)
- 给定的图是一棵树。
输入
输入由标准输入按以下格式给出:
N
a_1 b_1
:
a_{N-1} b_{N-1}
输出
打印最小值 k 使得给定的树是一棵统一树 k.
示例输入 1
7 1 2 2 3 2 4 4 6 6 7 7 5
示例输出 1
2
团结之树 1 由顶点组成 1, 2, 3 和 4 可以由以下内容构建:一棵统一树 0 由顶点组成 1,一棵团结之树 0 由顶点组成 3,一棵团结之树 0 由顶点组成 4,和顶点 2.
团结之树 1 由顶点组成 5 和 7 可以由以下内容构建:一棵统一树 1 由顶点组成 5,和顶点 7.
团结之树 2 由顶点组成 1, 2, 3, 4, 5, 6 和 7 可以由以下内容构建:一棵统一树 1 由顶点组成 1, 2, 3 和 4,一棵团结之树 1 由顶点组成 5 和 7,和顶点 6.
示例输入 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
3