Trova il centro di un albero
Ti vengono date
n città collegate fra loro tramite n-1 strade. Tutte le città sono connesse tra loro (eventualmente passando attraverso altre città). Vuoi assicurarti che la capitale si trovi nella posizione migliore possibile.Decidi che la posizione ideale è quella che riduce al minimo la distanza più grande dalle città di confine (ossia, le città collegate a una sola città). Quali città rappresentano i candidati migliori per diventare la capitale?
Input
La prima riga dell’input contiene un singolo intero
v (1 ≤ v ≤ 100 000).Le successive
v-1 righe contengono coppie di interi v1, v2 (1 ≤ v1, v2 ≤ v) che indicano che il vertice v1 è collegato al vertice v2 e viceversa.Output
Il programma deve stampare i migliori candidati per la capitale in ordine crescente.
Esempi
Input | Output |
4
1 2
2 3
3 4 | 2 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB