Fişierul intrare/ieşire:sediu.in, sediu.outSursă.campion 2003
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.05 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Sediu

Intr-o tara exista N orase, legate intre ele prin sosele, precum si o grupare terorista care ameninta securitatea nationala. Fiecare sosea leaga o pereche de orase si este bidirectionala. Sistemul stradal este astfel alcatuit, incat intre oricare doua orase exista exact un singur drum, mergand pe soselele din cadrul sistemului. Guvernul tarii a decis sa amplaseze sediul central al armatei intr-unul din orase, in asa fel incat sa minimizeze numarul de orase controlate de gruparea terorista. Aceasta poate controla orice submultime a celorlalte N-1 orase, in asa fel incat intre oricare doua orase controlate se poate circula, mergand pe soselele din cadrul sistemului stradal, fara a trece prin orasul in care este situat sediul central al armatei. Dupa ce armata isi amplaseaza sediul central intr-unul din orase, gruparea terorista alege un numar maxim posibil de orase pe care sa le controleze, care respecta proprietatea anterioara.

Cerinta

Determinati toate orasele in care armata isi poate amplasa sediul central, astfel incat numarul de orase controlate de gruparea terorista sa fie minim.

Date de intrare

Prima linie a fisierului de intrare sediu.in contine numarul intreg N. Pe urmatoarele N-1 linii se afla numerele a doua orase diferite, a si b, cu proprietatea ca exista o sosea care leaga orasele a si b.

Date de iesire

Prima linie a fisierului de iesire sediu.out va contine doua numere intregi O si M. O reprezinta numarul minim de orase controlate de gruparea terorista si M reprezinta numarul oraselor care pot fi alese drept sediu central si pentru care se obtine valoarea O. Pe urmatoarea linie vor fi afisate M numere intregi, separate prin spatii, reprezentand numerele oraselor in care se poate amplasa sediul central al armatei. Aceste numere vor fi afisate in ordine crescatoare.

Restrictii

  • 1N16.000

Exemplu

sediu.insediu.out
7
1 2
2 3
2 4
1 5
5 6
6 7
3 1
1

Explicatii

Daca sediul central al armatei este amplasat in orasul 1, gruparea terorista poate controla orasele 2, 3 si 4 sau 5, 6 si 7.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content