Se considera un arbore (graf neorientat, conex si aciclic) cu N vârfuri.
In nodurile acestui arbore locuiesc oameni, iar muchiile au lungime 1.
Se doreste înfiintarea in noduri ale arborelui a K puncte de salvare,
astfel încât locuitorii arborelui sa fie ajutati cât mai rapid
în caz de urgente.
La aparitia unei urgente într-un anumit nod, o masina a Salvarii pleaca
dintr-unul din cele mai apropiate puncte de salvare catre nodul respectiv, pentru
a acorda primul ajutor, dupa care se întoarce la punctul de plecare. Timpul
de rezolvare a unei urgente este dat de numarul de muchii parcurse de la punctul
de salvare la nodul în care a aparut urgenta.
Se considera ca pâna la întoarcerea salvarii în punctul de
plecare nu pot aparea urgente noi.
Cerinta
Sa se stabileasca nodurile în care se vor înfiinta puncte de salvare,
astfel încât orice urgenta sa fie rezolvabila în timp minim
(mai exact, maximul M al timpilor de rezolvare sa fie minim).
Date de intrare
Prima linie a fisierului de intrare salvare.in
contine numarul întreg N, reprezentând numarul de vârfuri
ale arborelui. A doua linie a fisierului contine numarul întreg K, reprezentând
numarul de puncte de salvare. Urmatoarele N-1 linii contin câte doi întregi
distincti a si b, separati printr-un spatiu, având semnificatia ca exista muchie între vârful numerotat cu a si cel numerotat cu b.
Date de iesire
În fisierul salvare.out
veti afisa pe prima linie numarul M, maximul timpilor de rezolvare.
Restrictii si precizari
1 <= N <= 1000
1 <= K <= 300 si K <= N
Vârfurile sunt numerotate cu numere distincte între 1 si
N.
Daca exista mai multe solutii, se va afisa una oarecare.
Exemplu
salvare.in
salvare.out
5
2
4 1
1 3
1 2
4 5
1
Explicatie
Timpul maxim de rezolvare este 1. Se înfiinteaza doua puncte de salvare,
în nodurile 1 si 4. Salvarea din 1 rezolva urgentele din 1 în timp
0 si urgentele din 2 si 3 în timp 1. Salvarea din 4 rezolva urgentele
din 4 în timp 0 si urgentele din 5 în timp 1. Exista si alte solutii.