← 返回题目列表

AtCoder · agc009_d

D. 团结

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

分数: 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