== include(page="template/taskheader" task_id="capitala") ==
!>problema/capitala?tree.png!
Imperiul Roman se clatină sub atacurile barbarilor! Harta imperiului conține $N$ orașe și drumuri de legătură. Oricare drum poate fi parcurs într-o zi. Din eficiență, romanii au construit numărul minim necesar de drumuri pentru a putea călători între oricare două orașe. Orașele de la marginea imperiului se numesc avanposturi și au un singur drum de legătură.
Pentru a proteja administrația, romanii doresc să mute capitala într-un oraș cât mai depărtat de avanposturi: distanța de la acel oraș până la cel mai apropiat avanpost trebuie să fie maximă. Ajutați-i să găsească toate orașele care maximizează această distanță.
Poveste și cerință...
h2. Date de intrare
Fișierul de intrare $capitala.in$ conține pe prima linie numărul $N$ de orașe. Pe următoarele $N-1$ linii sunt date perechi de numere $x y$ cu semnificația că între orașele $x$ și $y$ există un drum. Orașele sunt numerotate de la 1 la [$N$].
Fișierul de intrare $capitala.in$ ...
h2. Date de ieșire
În fișierul de ieșire $capitala.out$ se vor tipări, pe prima linie, distanța maximă până la un avanpost și numărul de orașe care au această distanță, separate printr-un spațiu. Pe linia a doua se vor tipări, în ordine crescătoare, numerele orașelor care obțin această distanță, separate prin spații.
În fișierul de ieșire $capitala.out$ ...
h2. Restricții
* $3 ≤ N ≤ 100.000$
* Pentru 40% din teste, $3 ≤ N ≤ 5.000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. capitala.in |_. capitala.out |
| 10
6 4
8 1
1 5
4 10
9 6
1 7
3 7
2 6
6 3
| 2 2
3 7
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
Orașul 3 are distanța 2 până la cele mai apropiate avanposturi (orașele 2 și 9). Orașul 7 are distanța 2 până la cele mai apropiate avanposturi (orașele 5 și 8). Toate celelalte orașe sunt la distanță 1 de cel mai apropiat avanpost (1, 4, 6) sau sunt ele însele avanposturi (2, 5, 8, 9, 10).
...
== include(page="template/taskfooter" task_id="capitala") ==
