题目描述

高桥国有 $N$ 个城镇，分别命名为城镇 $1$、城镇 $2$、$\ldots$、城镇 $N$。这个国家有 $N-1$ 条道路，第 $i$ 条道路双向连接城镇 $u_i$ 和城镇 $v_i$。对于任意两个城镇 $a$ 和 $b$，都可以通过若干条道路从城镇 $a$ 到达城镇 $b$。

高桥国王打算将某条信息传遍全国。由于事务繁忙，国王最多只能直接将信息传达给 $K$ 个城镇。

国王完成信息传达的瞬间记为时刻 $0$。对于 $t=1,2,3,\cdots$，会发生如下现象：

• 对于通过一条道路直接相连的城镇对 $a$ 和 $b$，如果在时刻 $t-0.5$ 时城镇 $a$ 已经获得信息，而城镇 $b$ 尚未获得信息，则在时刻 $t$ 时城镇 $b$ 也会获得信息。

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

输入格式

输入以如下格式从标准输入读入。

$N$ $K$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

输出格式

请输出答案。

样例 1

输入

5 2
1 2
2 3
3 4
4 5

输出

1

样例 2

输入

5 1
1 2
1 3
1 4
5 4

输出

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

说明/提示

限制条件

• 输入均为整数。
• $1 \leq K < N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 对于任意两个城镇 $a$ 和 $b$，都存在一条路径可以从 $a$ 到达 $b$。

样例解释 1

如果国王选择将信息直接传达给城镇 $2$ 和城镇 $4$，则城镇 $1$、$\ldots$、城镇 $5$ 首次获得信息的时刻分别为 $1, 0, 1, 0, 1$。此时，全国所有城镇都获得信息的最早时刻为 $1$，且可以证明这是最小可能值。

由 ChatGPT 4.1 翻译