tree     

Se considera o arborescenta (arbore cu radacina) formata din N noduri, numerotate de la 1 la N. Nodul 1 este considerat radacina.

Cerinta
Scrieti un program care sa determine numarul minim de arce care trebuie eliminate pentru a obtine un subarbore cu P noduri. Subarborele obtinut nu trebuie sa contina neaparat nodul 1.

Date de intrare
Fisierul de intrare tree.in contine pe prima linie numerele naturale N si P, separate printr-un spatiu.
Urmatoarele N -1 linii contin fiecare câte doua numere I si J, cuprinse între 1 si N, separate printr-un spatiu, cu semnificatia ca nodul J este descendent direct al nodului I (exista arc de la I la J).

Date de iesire
In fisierul de iesire tree.out va contine o singura linie pe care se va scrie numarul natural  X reprezentand numarul de arce eliminate (minim posibil).

Restrictii
1 <=P <= N <= 150
0 <= X <= N-1


Exemplu

tree.in tree.out Explicatie

11 6
1 2
2 6
2 7
2 8
1 3
1 4
4 9
4 10
4 11
1 5

 2

De exemplu, se elimina arcele 1 5 si 1 4.
Aceasta nu este singura solutie (de exemplu, s-ar putea elimina si arcele 1 5 si 1 2).

 

Timp maxim de executie/test : 0.1 secunde

prof. Dana Lica
Colegiul National “Ion.Luca Caragiale” Ploiesti
Contact: danal182001@yahoo.com