201164: [AtCoder]ARC116 E - Spread of Information

Problem Statement

Takahashi Kingdom has $N$ towns, called Town $1$ through $N$. There are $N-1$ roads in this kingdom. The $i$-th road connects Town $u_i$ and Town $v_i$ bidirectionally. For any two towns $a$ and $b$, it is possible to get from Town $a$ to Town $b$ by traversing some roads.

Takahashi, the king, wants to spread some information all over the kingdom. Since he is busy, he can directly transmit this information to at most $K$ towns.

Assume that Takahashi finishes transmitting the information at time $0$. Then, for each $t = 1, 2, 3, \cdots$, the following happens:

• For towns $a$ and $b$ directly connected by a road, if $a$ has already received the information at time $t - 0.5$ but $b$ has not, $b$ receives it at time $t$.

Takahashi wants to choose the $K$ towns to transmit the information to minimize the time taken until every town receives it. Find the minimum time this takes.

Constraints

• All values in input are integers.
• $ 1 \leq K < N \leq 2 \times 10^5$
• $ 1 \leq u_i, v_i \leq N$
• For any two towns $a$ and $b$, it is possible to get from Town $a$ to Town $b$ by traversing some roads.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

5 2
1 2
2 3
3 4
4 5

Sample Output 1

1

If Takahashi directly transmits the information to Town $2$ and $4$, Town $1, 2, 3, 4, 5$ receives it at time $1, 0, 1, 0, 1$, respectively. In this case, the information is spread all over the kingdom at time $1$. We can prove that this is the earliest possible time.

Sample Input 2

5 1
1 2
1 3
1 4
5 4

Sample Output 2

2

Sample Input 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

Sample Output 3

3