Керівник організації#5366

Керівник організації

1 секунда

128 мегабайтів

Дуже легка

В певній організації є $n$ осіб. З часом було встановлено, хто з ким безпосередньо спілкується в межах організації. На основі цих зв’язків відомо, що структура прямих комунікацій утворює дерево. Керівник організації знаходиться в корені цього дерева, а кожна особа має безпосередніх підлеглих, які відповідають дітям у дереві. Особа спілкується лише зі своїми безпосередніми підлеглими та своїм безпосереднім начальником.

Однак, хоча всі зв’язки відомі, невідомо, хто займає найвищу позицію в ієрархії. Тож відомі лише неорієнтовані канали спілкування, які утворюють структуру дерева, але корінь (керівник організації) невідомий.

Припустимо, що керівник організації прагне максимізувати свій вплив. Існує припущення, що керівником є та особа, для якої, якщо її видалити з мережі комунікацій, найбільша з решти об'єднаних груп осіб буде найменшою можливою. Знайдіть усіх можливих кандидатів на посаду керівника організації.

Вхідні дані

У першому рядку задано кількість осіб $n$ ( $2 \leq n \leq 50000$ 2 \leq n \leq 50000). Особи пронумеровані від $1$ до $n$ . Кожен з наступних $n - 1$ n - 1 рядків містить два числа $a_{i}$ a_i, $b_{i}$ b_i, які означають, що особи $a_{i}$ a_i і $b_{i}$ b_i спілкуються безпосередньо. Гарантується, що сукупність каналів зв’язку утворює дерево.

Вихідні дані

В одному рядку виведіть номери всіх можливих кандидатів на посаду керівника організації у зростаючому порядку, розділені пробілами.

Приклади

Приклад 1