Олимпиадный тренинг

Задача . D. Полное зеркало

Задача

Темы: Деревья Конструктив реализация дп поиск в глубину и подобное *2400 хэши

Дерево состоит из $n$ вершин. Выберите одну вершину как корень. Он должен удовлетворять условию ниже.

Для каждой пары вершин $v_{1}$ и $v_{2}$, если $distance$($root$, $v_{1}$) $= distance$($root$, $v_{2})$, тогда $degree$($v_{1}$) $= degree$($v_{2}$), где $degree$ — количество смежных вершин, а $distance$ — количество ребер между двумя вершинами.

Определите и найдите, есть ли такой корень в дереве. Если есть несколько ответов, выведите любой из них.

Входные данные

Первая строка содержит одно целое число $n$ ($1 \le n \le 10^{5}$) — количество верши.

Каждая из следующих $n-1$ строк содержит два целых числа $v_{i}$ и $u_{i}$ ($1 \le v_{i} \lt u_{i} \le n$), которые значат, что существует ребра между вершинами $v_{i}$ и $u_{i}$. Гарантируется, что граф — дерево.

Выходные данные

Если такой корень существует, выведите любой из них. Иначе выведите $-1$.

Примечание

Рисунок до первого примера. $1$, $5$, $7$ — также могут быть корнями.