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.2 sec | Limită de memorie | 4096 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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).