AT_arc116_e [ARC116E] Spread of Information

高桥国有 $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 \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 翻译