Farmer John mantiene instancabilmente le mucche in forma sui sentieri del pascolo. Vertici e archi bidirezionali hanno esattamente un cammino semplice fra ogni coppia, simili a un albero. Tutti gli archi tortuosi hanno sorprendentemente uguale lunghezza.

Le mucche astute chiamano lunghezza la massima distanza fra due vertici di un insieme. Se troppo grande rifiutano ogni esercizio.

Mappa $V$ vertici ($2 \le V \le 100,000$), numeri $1..V$. Bloccare fra due crea più insiemi e riduce entrambe le lunghezze.

Da albero totalmente connesso, $S$ blocchi ($1 \le S \le V-1$) danno $S+1$ insiemi. Scegli per minimizzare la massima lunghezza fra tutti.

Tutti i $V-1$ archi collegano $A_{i}$ ($1 \le A_{i} \le V$), $B_{i}$ ($1 \le B_{i} \le V; A_{i} \ne B_{i}$).

Esempio lineare di 7 vertici:

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

Due blocchi possibili: 1---2 | 3---4 | 5---6---7

Lunghezza massima $2$, risposta ottima, non migliorabile.

Limite di tempo: 2 secondi

Limite di memoria: 32 MB

Input

• Riga 1: due interi $V$, $S$ separati da spazio.
• Righe $2..V$: due interi $A_{i}$, $B_{i}$ separati da spazio.

Output

• Riga 1: intero, migliore lunghezza massima con $S$ blocchi.

Esempi

Input 1

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

Output 1

2

Autore del problema: Michael Cohen, 2010