e-olymp
Competitions

DFS. Articulation points. Bridges

Crossroad

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

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

Входные данные

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

Выходные данные

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

Time limit 1 seconds
Memory limit 122.28 MiB
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, г. Киев