Farmer John hält Kühe unermüdlich mit Übungen auf Weidewegen fit. Knoten mit bidirektionalen Kanten haben zwischen jedem Paar genau einen einfachen Pfad, ähneln also einem Baum. Alle gewundenen Kanten sind überraschend gleich lang.

Kluge Kühe nennen die größte Entfernung zwischen zwei Knoten einer Wegmenge ihre Pfadlänge. Ist sie zu groß, verweigern sie jegliche Übung.

$V$ Knoten ($2 \le V \le 100,000$), Nummern $1..V$, wurden kartiert. Sperren zwischen zwei Knoten schaffen mehr Mengen und verkürzen beide Pfadlängen.

Aus einem vollständig verbundenen Baum schaffen $S$ Sperren ($1 \le S \le V-1$) $S+1$ Mengen. Wähle so, dass ihre größte Pfadlänge minimal wird.

Alle $V-1$ Kanten verbinden $A_{i}$ ($1 \le A_{i} \le V$), $B_{i}$ ($1 \le B_{i} \le V; A_{i} \ne B_{i}$).

Lineares Beispiel mit 7 Knoten:

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

Zwei Sperren könnten so aussehen: 1---2 | 3---4 | 5---6---7

Größte Pfadlänge $2$, optimal, besser geht nicht.

Zeitlimit: 2 Sekunden

Speicherlimit: 32 MB

Eingabe

• Zeile 1: zwei Ganzzahlen $V$, $S$ durch Leerzeichen getrennt.
• Zeilen $2..V$: zwei Ganzzahlen $A_{i}$, $B_{i}$ durch Leerzeichen getrennt.

Ausgabe

• Zeile 1: Ganzzahl, bestmögliche maximale Pfadlänge bei $S$ Sperren.

Beispiele

Eingabe 1

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

Ausgabe 1

2

Aufgabenautor: Michael Cohen, 2010