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

消息传递

题目描述

高桥国有 $N$ 个城镇，通过 $N-1$ 条道路构成一棵树（任意两城镇间有且仅有一条路径）。第 $i$ 条道路双向连接城镇 $u_i$ 和 $v_i$。

国王计划将信息传遍全国，规则如下：

1. 国王最多可直接将信息传达给 $K$ 个城镇（初始传递点），该操作在时刻 $0$ 完成；
2. 从时刻 $t=1$ 开始，每个时刻会发生信息扩散：对于直接相连的城镇对 $a$ 和 $b$，若时刻 $t-0.5$ 时 $a$ 已获得信息且 $b$ 未获得，则时刻 $t$ 时 $b$ 会获得信息。

国王会选择最优的 $K$ 个初始传递点，使得所有城镇获得信息的最大时间最小化。请输出这个最小的最大时间。

输入格式

第一行输入两个整数 $N$ 和 $K$； 接下来 $N-1$ 行，每行输入两个整数 $u_i$ 和 $v_i$，表示第 $i$ 条道路连接的两个城镇。

输出格式

输出所有城镇获得信息的最小最大时间。

样例

样例输入 1

5 2
1 2
2 3
3 4
4 5

样例输出 1

1

样例解释 1

选择城镇 2 和 4 作为初始传递点：

• 时刻 0：城镇 2、4 获得信息；
• 时刻 1：城镇 1（从 2 扩散）、3（从 2 或 4 扩散）、5（从 4 扩散）获得信息； 所有城镇的最大获得时间为 1，且无法更小。

样例输入 2

5 1
1 2
1 3
1 4
5 4

样例输出 2

2

样例解释 2

选择城镇 1 作为初始传递点：

• 时刻 0：城镇 1 获得信息；
• 时刻 1：城镇 2、3、4 获得信息；
• 时刻 2：城镇 5 获得信息； 最大时间为 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 \leq K < N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 输入保证城镇与道路构成一棵树（连通且无环）
• 所有输入值均为整数

子任务