#2961. 组件网络

组件网络

题目描述

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

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

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

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

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

输入格式

N LN\ L u1 v1u_1\ v_1 u2 v2u_2\ v_2 ... uL vLu_L\ v_L

输出格式

DD

样例

样例输入 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<=10N <= 10
  • 14 pts,满足 N<=100N <= 100
  • 76 pts,满足 N<=100000N <= 100000
  • 对于 100% 的数据,满足 1<=ui,vi<=N, N<=100000, L<=N11 <= u_i, v_i <= N,\ N <= 100000,\ L <= N-1