== include(page="template/taskheader" task_id="sediu") ==
==Include(page="template/taskheader" task_id="sediu")==
Poveste ...
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.
h2. Cerinta
...
h2. Restrictii
...
Determinati toate orasele in care armata isi poate amplasa sediul central, astfel incat numarul de orase controlate de gruparea terorista sa fie minim.
h2. 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$.
h2. 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.
h2. Restrictii
* $1$ ≤ $N$ ≤ $16.000$
h2. Exemplu
| sediu.in | sediu.out |
| linia1
linia2
linia3
| linia1
linia2
|
table(example). |_. sediu.in |_. sediu.out |
| 7
1 2
2 3
2 4
1 5
5 6
6 7
| 3 1
1 |
== include(page="template/taskfooter" task_id="sediu") ==
h3. 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$}.
==Include(page="template/taskfooter" task_id="sediu")==
