| Fişierul intrare/ieşire: | capitala.in, capitala.out | Sursă | Cerc informatică Vianu |
| Autor | Catalin Francu | Adăugată de |  Catalin Francu •Catalin.Francu |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 4096 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Poti vedea testele pentru aceasta problema accesand atasamentele.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).
