Find the Center of a Tree
You are given
n cities that are connected to each other with n-1 roads. All the cities are connected to each other (maybe through other cities). You would like to make sure the capital is at the best possible location.You decide that the best location is the one that minimizes the furthest distance from the borderline cities (the cities that are only connected to 1 city). Which cities would be the best candidates for the capital?
Input
The first line of the input contains a single integer
v (1 ≤ v ≤ 100 000).The following
v-1 lines contain pairs of integers v1, v2 (1 ≤ v1, v2 ≤ v) which means that the vertex v1 is connected to the vertex v2 and vice versa.Output
The program should print the best candidates for the capital in increasing order.
Examples
Input | Output |
4
1 2
2 3
3 4 | 2 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB