judete

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 2 orase din tara. Nefiind in stare sa administreze toate orasele presedintele hotaraste urmatoarele:

  1. tara va fi impartita intr-un numar de judete, astfel incat fiecare oras sa apartina exact unui judet
  2. drumul dintre oricare 2 orase din acelasi judet nu trece prin orase din alt judet
  3. 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

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).

Timp maxim de executie/test: 0.1 secunde

Fechete Dan Ionut
Universitatea Bucuresti
Facultatea de Matematica si Informatica
mailto:f_dany@eminem.com