树是一个没有循环的连通图。一棵树的叶子是与另一个顶点精确连接的任何顶点。
给你一棵有 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