信息传播

时间限制：3s
空间限制：1024MB

题目描述

高桥国有 $N$ 个城镇和 $N-1$ 条双向道路，第 $i$ 条道路连接城镇 $u_i$ 与 $v_i$，任意两个城镇之间均可互相到达。国王最多可以在时刻 $0$ 直接把信息传给 $K$ 个城镇；此后每经过一个单位时间，已经获知信息的城镇都会把信息传给所有相邻城镇。

国王可以自行选择初始城镇。求所有城镇都获知信息所需时间的最小值。

输入格式

第一行两个整数 $N,K$，接下来 $N-1$ 行每行两个整数 $u_i,v_i$，表示一条道路。

输出格式

输出最小时间。

样例输入 1

5 2
1 2
2 3
3 4
4 5

样例输出 1

1

样例输入 2

5 1
1 2
1 3
1 4
5 4

样例输出 2

2

样例输入 3

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

样例输出 3

3

数据范围

• $1\le K<N\le 2\times 10^5$；
• $1\le u_i,v_i\le N$；
• 输入的道路构成一棵树。