Fișierul intrare/ieșire	capitala.in, capitala.out	Sursă	Cerc informatică Vianu
Autor	Cătălin Frâncu	Adăugată de	Cătălin Frâncu • Catalin.Francu
Timp de execuție pe test	0.05 sec	Limită de memorie	4096 KB
Scorul tău	N/A	Dificultate	2.25

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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ță.

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.

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.

Restricții

• 3 ≤ N ≤ 100.000
• Pentru 30% din teste, 3 ≤ N ≤ 5.000

Exemplu

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 sau sunt ele însele avanposturi.