Дерево состоит из \(n\) вершин. Выберите одну вершину как корень. Он должен удовлетворять условию ниже.
Определите и найдите, есть ли такой корень в дереве. Если есть несколько ответов, выведите любой из них.
Первая строка содержит одно целое число \(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\) — также могут быть корнями.
Рисунок до второго примера. Невозможно найти корень графа.
7 1 2 2 3 3 4 4 5 3 6 6 7
3
6 1 3 2 3 3 4 4 5 4 6
-1
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач