kdtree

Kilikinei îi plac mult arborii. De data aceasta ea a definit un KDtree ca fiind un arbore pentru care distanţa între oricare două noduri este mai mică sau egală cu $K$. Acum, Kilikina are un arbore cu $N$ noduri şi se întreabă care este numărul minim de muchii pe care trebuie să le taie din arbore, astfel încât toţi arborii rămaşi să fie KDtrees.

Cerinţă

Scrieţi un program care poate răspunde la întrebarea Kilikinei.

Date de intrare

Pe prima linie a fişierului de intrare kdtree.in se vor afla două numere naturale $N$ şi $K$ având semnificaţiile din enunţ. Următoarele $N-1$ linii vor conţine câte două numere $x$ şi $y$, reprezentând faptul că există o muchie între nodurile $x$ şi $y$ din arbore.

Date de ieșire

În fişierul de ieşire kdtree.out veţi afişa un singur număr reprezentând numărul minim de muchii ce trebuiesc tăiate din arbore astfel încât toţi arborii rămaşi să fie KDtrees.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $1 \leq K \leq 200 \ 000$
• Pentru $40\%$ din teste $N \leq 1 \ 000$ şi $K \leq 50$
• Pentru $70\%$ din teste $N \leq 100 \ 000$ şi $K \leq 100$
• Distanţa între două noduri $x$ şi $y$ din arbore este egală cu numărul de muchii aflate pe drumul dintre $x$ şi $y$

Exemplu

kdtree.in

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

kdtree.out

1

Explicație

Se va tăia o singură muchie, muchia $1-2$, astfel încât cei doi arbori rămaşi formaţi din nodurile $(1, 3, 4)$ şi $(2, 5, 6)$ au distanţa între oricare două noduri mai mică sau egală cu $K=2$.