Farmer John niestrudzenie dba o formę krów ćwiczących na drogach pastwisk. Wierzchołki z dwukierunkowymi krawędziami mają dokładnie jedną prostą ścieżkę między każdą parą, przypominając drzewo. Wszystkie kręte krawędzie mają zaskakująco równą długość.

Sprytne krowy nazywają największą odległość między dwoma wierzchołkami zbioru długością ścieżki. Za duża powoduje odmowę ćwiczeń.

Zmapował $V$ wierzchołków ($2 \le V \le 100,000$), numery $1..V$. Blokując drogę między dwoma, tworzy więcej zbiorów i zmniejsza obie długości.

Z całkowicie połączonego drzewa $S$ blokad ($1 \le S \le V-1$) tworzy $S+1$ zbiorów. Wybierz, by minimalizować największą długość wszystkich.

Wszystkie $V-1$ krawędzi łączą $A_{i}$ ($1 \le A_{i} \le V$), $B_{i}$ ($1 \le B_{i} \le V; A_{i} \ne B_{i}$).

Liniowy przykład 7 wierzchołków:

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

Możliwe dwie blokady: 1---2 | 3---4 | 5---6---7

Maksymalna długość $2$ to optimum, lepiej nie można.

Limit czasu: 2 sekundy

Limit pamięci: 32 MB

Wejście

• Wiersz 1: dwie liczby całkowite $V$, $S$ rozdzielone spacją.
• Wiersze $2..V$: dwie liczby całkowite $A_{i}$, $B_{i}$ rozdzielone spacją.

Wyjście

• Wiersz 1: jedna liczba całkowita, najlepsza maksymalna długość przy $S$ blokadach.

Przykład

Wejście 1

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

Wyjście 1

2

Autor zadania: Michael Cohen, 2010