EduBrick

N. Центр дерева

3000 мс · 256 МБ · всё или ничего

Дано дерево. Найдите его центр — вершину, у которой наибольшее расстояние до других вершин минимально.

У дерева центров может быть один или два. Выведите все по возрастанию номера.

Перебирать вершины нельзя. Приём тот же, что с диаметром: двумя обходами находится диаметральный путь, а центр лежит ровно посередине него.

Формат ввода

Первая строка содержит число nn (1≤n≤1051 \le n \le 10^5).

Далее идут n−1n - 1 строк с рёбрами дерева.

Формат вывода

Номера центров по возрастанию через пробел.

Примеры

ввод
4
1 2
2 3
3 4
вывод
2 3
ввод
3
1 2
2 3
вывод
2
Войдите, чтобы отправлять решения.