该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

实验室新进了 $N$ 台计算机，老师安排你给他们搭一个局域网，使得互相连接。

这还不简单，你拿来 $N-1$ 条网线，打算像模像样地把它们随便勾搭一下。 “只要连通就好了吧。”你是这样想的。

连了其中 $L$ 条网线后，你打算休息一会，找了两台已经连通的计算机联机玩游戏，然后你发现，时延很高，ping 很慢。

你意识到了问题所在“我应该想办法让最远的两台电脑尽量近啊”。

问怎样连结剩下的网线，可以使得整个组建好的网络里最远的两台计算机距离尽量小，求最小的距离 $D$。

输入格式

$N\ L$ $u_1\ v_1$ $u_2\ v_2$ ... $u_L\ v_L$

输出格式

$D$

样例

样例输入 1

6 4
1 2
1 3
4 5
4 6

样例输出 1

3

样例输入 2

50 15
1 2
2 3
3 4
4 5
5 6
7 8
8 9
9 10
10 11
11 12
13 14
14 15
15 16
16 17
17 18

样例输出 2

8

提示

• 10 pts，满足 $N <= 10$；
• 14 pts，满足 $N <= 100$；
• 76 pts，满足 $N <= 100000$；
• 对于 100% 的数据，满足 $1 <= u_i, v_i <= N,\ N <= 100000,\ L <= N-1$。

---