Fișierul intrare/ieșire capitala.in, capitala.out Sursă Cerc informatică Vianu
Autor Cătălin Frâncu Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.2 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Capitala

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 40% din teste, 3 ≤ N ≤ 5.000

Exemplu

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

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

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii