judete

Judete

== include(page="template/taskheader" task_id="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

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:

* tara va fi impartita intr-un numar de judete, astfel incat fiecare oras sa apartina exact unui judet
* drumul dintre oricare $2$ orase din acelasi judet nu trece prin orase din alt judet

Fie $T$ maximul dintre numarul de orase apartinand aceluiasi judet.

h2. Cerinta
 
Scrieti un program care sa gaseasca o impartire in judete cu $T$ minim pentru o configuratie de orase si sosele date.

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

h2. Date de iesire

...

Prima linie a fisierului $judete.out$ va contine $T$ minim pentru configuratia din fisierul de intrare.

h2. Restrictii

* $... ≤ ... ≤ ...$

* $3 ≤ K ≤ N ≤ 127$
* pe soselele din tara maimutelor se circula in ambele sensuri.

h2. Exemplu
table(example). |_. judete.in |_. judete.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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

|
h3. Explicatie

...

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

== include(page="template/taskfooter" task_id="judete") ==

1759