Fişierul intrare/ieşire:capitala.in, capitala.outSursăCerc informatică Vianu
AutorCatalin FrancuAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.incapitala.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 sa te autentifici pentru a trimite solutii. Click aici