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

Трубы

Трубы

Лимит времени 1 секунда
Лимит использования памяти 16 MiB

На земле Кахутов Ломикель - бог труб. Он управляет водопроводными трубами, стоками, канализацией и, возможно, даже туннелями метро. Кахуты поклоняются ему в многочисленных священных источниках, которые связаны огромной сетью церемониальных труб. Каждая труба напрямую соединяет два истока.

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

Иногда гнев Ломикеля приводит к разрыву трубы, поэтому сантехнику приходится использовать другие трубы, чтобы вода обошла сломанную. Это не всегда возможно - для некоторых каналов другого пути не существует. Эти трубы называются критическими, и сантехник должен уделять им особое внимание. Вы можете увидеть критические трубы, выделенные жирным на рисунке ниже.

Ваша задача - по описанию сети найти все критические каналы. Сеть достаточно обширная, а у вас ограниченный объем памяти. Ограничение по памяти в этой задаче 16 MB.

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

Первая строка содержит два целых числа n и m. Здесь n (1n10^5) - число истоков а m (1m6 * 10^6) - количество труб.

Каждая из следующих m строк описывает одну трубу. Она содержит два целых числа u и v (1u, vn) - номера источников, соединенных трубой.

Два истока могут быть соединены несколькими трубами, но конечные точки одной трубы всегда являются разными источниками.

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

Выведите последовательность строк. Каждая строка описывает один критический канал и содержит два целых числа, разделенных пробелом: конечные точки канала.

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

prb9040.gif

Пример

Входные данные #1
10 11
1 7
1 8
1 6
2 8
6 7
5 8
2 5
2 3
2 4
3 4
10 9
Выходные данные #1
1 8
9 10
Источник 2015 CEOI День 1, Задача C