Description

To keep the cows healthy, Farmer John makes the poor cows run back and forth along paths between pastures. The cows’ path system can be represented as a set of vertices and some bidirectional roads connecting pairs of vertices, such that between every pair of vertices there is exactly one simple path. In other words, the layout of these vertices forms a tree, and every edge has the same length, equal to $1$.

For a given cowpath set, the clever cows compute the maximum distance between any pair of vertices, which we call the diameter of this path set. If the diameter is too large, the cows will refuse to exercise.

Farmer John labels each vertex $1\cdots V(2\le V\le 10^5)$. To obtain a smaller diameter, he can choose to block some existing roads, thus producing more cowpath sets and potentially reducing the diameters of some of them. Starting from a tree, Farmer John may block $S(1\le S\le V-1)$ bidirectional roads, thereby obtaining $S+1$ cowpath sets.

Your task is to compute the best blocking plan so that the maximum diameter among all resulting cowpath sets is as small as possible. Farmer John gives you all $V-1$ bidirectional roads, each described as: vertices $A_i(1\le A_i\le V)$ and $B_i(1\le B_i\le V,A_i\ne B_i)$ are connected.

Input Format

Line 1: Two space-separated integers: $V$ and $S$.

Lines 2 to $V$: Two space-separated integers: $A_i$ and $B_i$.

Output Format

A single integer, the best possible maximum path length that FJ can achieve using $S$ blocked roads.

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

2 

Hint

Consider this rather linear cowpath set (a tree with 7 vertices):

1---2---3---4---5---6---7

If FJ can block two paths, he might choose them to make a map like this:

1---2 | 3---4 | 5---6---7 where the longest path length is 2, which would be the answer in this case. He can do no better than this.

Translated by ChatGPT 5