题目描述

Farmer John 有 $N$ 个牧场，这些牧场通过 $N-1$ 条道路连接，形成了一个树形结构。

但在 28 年的经营后（译者注：USACO 创办于 1992 年），FJ 觉得处理树上问题非常辣手，他认为一条链上的问题更加简单。

因此他决定将整棵树划分为若干条链，将每一条链的管理权授予一位工人。他不关心链的数量，却关心链的长度，他希望划分的链都尽可能长，从而不会有人用效率低下的算法蒙混过关。

FJ 现在想知道最大的正整数 $K$，使得整棵树被划分成若干条链，且每条链的长度都至少是 $K$。

输入格式

第一行一个整数 $N$（$1 \leq N \leq 10^5$）。

接下来 $N$ 行，每行两个整数 $u,v$（$1 \leq u,v \leq N$），描述一条连接 $u,v$ 的道路。

输出格式

输出 $K$。

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

3

提示

样例解释

一种划分方案如下：

子任务

• 测试点 $2 \sim 4$ 满足最多有一个点的度数大于 $2$。
• 测试点 $5 \sim 8$ 满足 $N \leq 10^3$。
• 测试点 $9 \sim 15$ 没有特殊限制。