Kilikinei îi plac mult arborii. De data aceasta ea a definit un KDtree ca fiind un arbore pentru care distanţa dintre 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 trebuie să fie tăiate din arbore astfel încât toţi arborii rămaşi să fie KDtrees.
Restricţii
• 1 ≤ N ≤ 200000
• 1 ≤ K ≤ 200000
• Distanţa între două noduri x şi y din arbore este egală cu numărul de muchii aflate pe drumul dintre x şi y.
Exemple
kdtree.in
kdtree.out
Explicaţii
6 2
1 2
1 3
1 4
2 5
2 6
1
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.