In tara maimutelor exista N
orase numerotate de la 1 la N.
Orasele sunt conectate prin sosele, astfel incat exista un drum unic intre oricare
doua orase din tara. Nefiind in stare sa administreze toate orasele presedintele
hotaraste urmatoarele:
tara va fi impartita intr-un numar de judete, astfel incat fiecare oras
sa apartina exact unui judet
drumul dintre oricare doua orase din acelasi judet nu trece prin orase din
alt judet
numarul minim de orase dintr-un judet este K
Fie T maximul dintre numarul de
orase apartinand aceluiasi judet.
Cerinta
Scrieti un program care sa
gaseasca o impartire in judete cu T minim pentru o configuratie de orase si sosele date.
Date de intrare
Pe prima linie a fisierului
de intrare judete.in sunt scrise
cele doua numere naturale N ,
K separate printr-un singur
spatiu.
Pe urmatoarele N-1 linii sunt
scrise cate doua numere naturale cuprinse intre 1
si N, separate prin spatiu, reprezentand
doua orase intre care exista o sosea.
Date de iesire
Prima linie a fisierului
judete.out va contine T minim pentru configuratia din fisierul de intrare.
Restrictii
2 < N, K < 128
Pe soselele din tara maimutelor se circula in ambele sensuri.
Exemplu
judete.in
judete.out
Explicatie
10 3
1 2
2 3
3 4
3 5
2 6
6 7
6 8
8 9
1 10
4
O impartire posibila
a oraselor in judete este:
1, 2,
10
3, 4,
5
6, 7,
8, 9
Fiecare oras apartine exact unui singur judet.
Fiecare judet contine cel putin 3
orase.
Numarul maxim de orase dintr-un judet este 4
(si acesta este minim posibil).
Fechete
Dan Ionut Universitatea Bucuresti
Facultatea de Matematica si Informatica mailto:f_dany@eminem.com