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

Перехрестя

Перехрестя

Ліміт часу 1 секунда
Ліміт використання пам'яті 122 MiB

Перший китайський імператор монгольської динас­тії Юань - Хубіла́й (онук Чингісхана), якого монголи прозивали кага́н Сеце́н - проводив завойов­ниць­кі війни. Тому постійно потребував грошей, які намагався отримати від купців, стягуючи мито. Хитрі купці часто обминали перехрестя з митарями. А завойовників-монголів було замало, щоб перекрити всі перехрестя. Тому митарів намагалися ставити так, щоб їх неможливо було оминути.

З’ясуйте, які перехрестя повністю розбивають систему шляхів на не зв’я­зані між собою складові.

Вхідні дані

prb7176

Всі пункти системи доріг - перехрестя й закінчення доріг - занумеровано послідовними натуральними числами у межах від 1 до деякого натураль­ного числа n (n1234567) включно. Кожний рядок містить пару натуральних чисел - номерів пунктів, які сполучено дорогою без пунктів між кінцями. Таким чином перераховано всі такі дороги по одному разу. Цими дорогами з будь-якого пункту можна потрапити у будь-який інший пункт. Кількість доріг не перевищує 1234567.

Вихідні дані

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

Приклад

Вхідні дані #1
1 2
1 4
1 5
2 5
2 3
3 6
3 7
4 5
6 7
Вихідні дані #1
2 3
Автор Олександр Рудик
Джерело ІІІ (міський) етап Всеукраїнської учнівської олімпіади з інформатики, 2014, м. Київ