Encontre o Centro de uma Árvore
Tem à sua disposição
n cidades ligadas entre si por n-1 estradas. Todas as cidades estão conectadas umas às outras (eventualmente através de outras cidades). Pretende garantir que a capital seja colocada na melhor localização possível.Decide que a melhor localização é aquela que minimiza a maior distância até às cidades fronteiriças (as cidades que estão ligadas apenas a uma outra cidade). Que cidades seriam as melhores candidatas para a capital?
Entrada
A primeira linha da entrada contém um único inteiro
v (1 ≤ v ≤ 100 000).As
v-1 linhas seguintes contêm pares de inteiros v1, v2 (1 ≤ v1, v2 ≤ v), indicando que o vértice v1 está ligado ao vértice v2 e vice-versa.Saída
O programa deve imprimir, por ordem crescente, os melhores candidatos para ser a capital.
Exemplos
Entrada | Saída |
4
1 2
2 3
3 4 | 2 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB