salvare

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;
- pe a doua linie K numere distincte intre 1 si N, ordonate crescator, nodurile în care se vor infiinta puncte de salvare.

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 1 4

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.