Problem Description

Country X has $n$ cities and $n - 1$ roads of length $1$. Each road connects two cities, and any two cities can reach each other through some roads. Obviously, the cities and roads form a tree.

The king of Country X decides to designate $k$ cities as the core cities of Country X, and the remaining cities are non-core cities. These $k$ core cities must satisfy the following two conditions:

1. These $k$ cities can reach each other pairwise via roads without passing through any non-core city.
2. Define the distance from a non-core city to the $k$ core cities as the minimum value among its distances to the $k$ core cities.

To measure traffic conditions, the king invented the traffic congestion level, which is the maximum value among the distances from all non-core cities to the core cities.

The problem is: how should we choose the core cities to minimize the traffic congestion level? Output the minimum possible traffic congestion level that satisfies the conditions.

Input Format

The first line contains $2$ positive integers $n, k$.

The next $n - 1$ lines each contain $2$ positive integers $u, v$, meaning there is a road of length $1$ between city $u$ and city $v$.

Constraints:

• $1 \le k < n \le 10 ^ 5$.
• $1 \le u, v \le n, u \ne v$, and it is guaranteed that the cities and roads form a tree.

Output Format

One line with one integer, representing the minimum traffic congestion level that satisfies the conditions.

6 3
1 2
2 3
2 4
1 5
5 6

1

Hint

[Sample Explanation]

Designate cities $1, 2, 5$ as the $3$ core cities. Then the distances from the other $3$ non-core cities $3, 4, 6$ to the core cities are all $1$, so the answer is $1$.

Translated by ChatGPT 5