eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Найдите центроид

Найдите центроид

Найдите любой центроид в дереве. \InputFile Первая строка содержит одно целое число $n$ $(1 ≤ n ≤ 2 · 10^5)$ — количество вершин. Каждая из следующих $n − 1$ строк содержит по два целых числа $v_i$ и $u_i$ $(1 ≤ v_i$ , $u_i ≤ n)$ — вершины, между которыми существует ребро. Гарантируется, что этот граф — дерево. \OutputFile Выведите номер вершины, которая является центроидом. Если центроидов несколько, выведите любой. \includegraphics{https://static.eolymp.com/content/fs/fsn3om7lol7tr7jrord7fd4744.gif}
Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
12
1 3
2 3
3 4
4 5
4 6
6 7
6 10
10 11
10 12
6 8
8 9
Выходные данные #1
6