Connected Core Cities

X country has \(n\) cities and \(n-1\) roads, forming a tree where every road has length 1. The king wants to choose \(k\) cities as core cities such that:

• The \(k\) core cities form a connected subgraph (i.e. every two core cities can be reached using only core cities).
• For every non–core city, define its distance to the core as the minimum distance from that city to any of the \(k\) core cities. Let \(R\) be the maximum such distance among all non–core cities. The core cities should be chosen so that \(R\) is minimized. The task is to output this minimum possible value of \(R\).

Note: If all cities are chosen as core (i.e. \(k=n\)), the answer is \(0\).

The problem can be seen as finding a connected \(k\)–vertex subset (i.e. a connected subtree with \(k\) vertices) for which the maximum distance from any vertex outside the subset to the subset is minimized. All distances are measured as the number of edges (each of length 1) on the unique simple path between cities.

inputFormat

The first line contains two integers \(n\) and \(k\) (\(1 \leq k \leq n\)). The next \(n-1\) lines each contain two integers \(u\) and \(v\) (1-indexed), indicating there is a road connecting city \(u\) and city \(v\). It is guaranteed that the cities form a tree.

outputFormat

Output a single integer, which is the minimum possible value of \(R\), the maximum distance from a non–core city to its nearest core city, among all choices of \(k\) connected core cities.

sample

4 1
1 2
2 3
2 4

1