← 返回题目列表

Codeforces · 622/E

E. 叶子里的蚂蚁

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

树是一个没有循环的连通图。一棵树的叶子是与另一个顶点精确连接的任何顶点。

给你一棵有 n 个顶点的树,根位于顶点 1。树的每片叶子上都有一只蚂蚁。一秒钟内,一些蚂蚁可以同时从它们所在的顶点到达父顶点。除了树的根之外,没有两只蚂蚁可以同时位于同一个顶点。

求所有蚂蚁到达树根所需的最短时间。请注意,一开始蚂蚁只在树叶中。

输入

第一行包含整数 n (2 ≤ n ≤ 5·105) — 树中的顶点数。

接下来的 n - 1 行中的每一行都包含两个整数 xi, yi (1 ≤ xi, yi ≤ n) — 第 i 条边的端点。保证您获得正确的无向树。

输出

打印唯一的整数 t — 所有蚂蚁到达树根所需的最短时间。

示例

输入 #1

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

输出 #1

6

输入 #2

2
2 1

输出 #2

1