配点 : $800$ 点

問題文

高橋国には $N$ 箇所の町があり、それぞれ町 $1$ 、町 $2$、 $\ldots$ 、町 $N$ と名付けられています。 この国には $N-1$ 本の道があり、 $i$ 本目の道は 町 $u_i$ と町 $v_i$ を双方向に結びます。任意の $2$ つの町 $a$, $b$ について、いくつかの道を通ることにより、町 $a$ から町 $b$ へ移動することが出来ます。

高橋国王は、ある情報を国土全体に流そうとしています。多忙な高橋国王は、 $K$ 箇所までの町にしか直接情報を伝達することが出来ません。

高橋国王の情報伝達が終わった瞬間を時刻 $0$ とします。 $t = 1, 2, 3, \cdots$ について、以下の現象が発生します。

• $1$ 本の道で直接結ばれている町の組 $a$, $b$ について、 時刻 $t-0.5$ に町 $a$ に情報が伝わっており、町 $b$ に情報が伝わっていないとき、 時刻 $t$ に町 $b$ にも情報が伝わる。

高橋国王は $K$ 箇所の連絡先を適切に選択し、全ての町に情報が伝わるまでに掛かる時間を最小化しようと考えています。最小値を答えてください。

制約

• 入力は全て整数
• $1 \leq K < N \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• 任意の $2$ つの町 $a$, $b$ について、いくつかの道を通ることにより、町 $a$ から町 $b$ へ移動することが出来る。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_{N-1}$ $v_{N-1}$

出力

答えを出力せよ。

5 2
1 2
2 3
3 4
4 5

1

高橋国王が町 $2$ と町 $4$ に直接情報を伝達した場合、町 $1$ 、 $\ldots$ 、町$5$ に初めて情報が伝わる時刻は、それぞれ $1, 0, 1, 0, 1$ となります。このとき、 国土全体に情報が広まるのは時刻 $1$ であり、これが達成可能な最小値であることが証明出来ます。

5 1
1 2
1 3
1 4
5 4

2

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