Contest Duration: - (local time) (120 minutes) Back to Home
E - Spread of Information /

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

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

制約

• 入力は全て整数
• 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}


入力例 1

5 2
1 2
2 3
3 4
4 5


出力例 1

1


入力例 2

5 1
1 2
1 3
1 4
5 4


出力例 2

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


Score : 800 points

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}


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