Fişierul intrare/ieşire:judete.in, judete.outSursă.campion 2005
AutorDan-Ionut FecheteAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.1 secLimită de memorie20096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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:

  • 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
  • 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

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

Exemplu

judete.injudete.out
10 3
1 2
2 3
3 4
3 5
2 6
6 7
6 8
8 9
1 10
4

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content