eolymp
bolt
Try our new interface for solving problems
Problems

Crossroad

Crossroad

Time limit 1 second
Memory limit 122 MiB

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

Выясните, какие перекрестки полностью разбивают систему путей на несвязные между собой составляющие.

Input data

prb7176

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

Output data

Единственная строка должна содержать в порядке возрастания номера всех пунктов, исключение каждого из которых (лишь одного) вместе с дорогами, которые из него выходят (входят в него), приводит к разбиению системы путей на несвязные между собой составляющие (минимум на две). Иначе говоря, после такого исключения перестает исполняться предпоследнее предложение описания входных данных. Купец не сможет обойти мытаря на таком перекрестке, если двигаться из одной составляющей системы дорог к другой. Входные данные гарантируют существование не менее одного такого перекрестка.

Examples

Input example #1
1 2
1 4
1 5
2 5
2 3
3 6
3 7
4 5
6 7
Output example #1
2 3
Author Oleksandr Rudyk
Source ІІІ (городской) этап Всеукраинской олимпиады школьников по информатике, 2014, г. Киев