Задачи
Обнаружитель тупика
Обнаружитель тупика
Совет Вашего родного города решил улучшить размещение дорожных знаков, особенно в тупиках. Они дали Вам дорожную карту, и Вы должны определить, где поставить знаки чтобы обозначить тупики. Они хотят, чтобы Вы использовали как можно меньше знаков.
Дорожная карта представляет собой набор перекрестков, соединенных улицами с двусторонним движением. Следующее правило описывает, как получить полное размещение знаков тупика. Рассмотрим улицу $S$, соединяющую место $x$ с другим местом. $x$-вход в $S$ становится тупиковым, если после входа в $S$ из $x$ невозможно вернуться в $x$ не делая разворот. Разворот --- это поворот на $180$ градусов, сразу же меняющий направление.
Для экономии затрат Вы решили не устанавливать лишние тупиковые знаки, как указано в следующем правиле. Рассмотрим улицу $S$ со знаком тупика на $x$-въезде и другую улицу $T$ со знаком тупика на $y$-въезде. Если после въезда в $S$ из $x$ можно достигнуть $y$ и въехать в $T$, не делая разворота, то знак тупика на $y$-вход улицы $T$ является избыточным. См. примеры на рисунке E.1.
\includegraphics{https://static.eolymp.com/content/1q/1qspidde3d4u15asushgof2b60.gif}
Рисунок E.1: Иллюстрация входных данных из примером с указанием места размещения неизбыточных знаков тупика.
\InputFile
Первая строка содержит два целых числа $n$ и $m$, где $n~(1 \le n \le 5 \cdot 10^5)$ --- количество перекрестков, а $m~(0 \le m \le 5 \cdot 10^5)$ --- количество улиц. Каждая из следующих $m$ строк содержит два целых числа $v$ и $w~(1 \le v < w \le n)$, обозначающих что улица с двусторонним движением соединяет перекрестки $v$ и $w$. Все улицы во входных данных различны.
\OutputFile
В первой строке выведите количество $k$ установленных тупиковых знаков. В каждой из следующих $k$ строк выведите два целых числа $v$ и $w$, обозначающие что на въезде $v$ на улицу, соединяющую перекрестки $v$ и $w$, необходимо установить знак тупика. Строки, описывающие тупиковые знаки, должны быть отсортированы в порядке возрастания $v$, а при равных значениях --- в порядке возрастания $w$.
\includegraphics{https://static.eolymp.com/content/98/98o8dfl2hh2c1fdpldt758pb94.gif}
Входные данные #1
6 5 1 2 1 3 2 3 4 5 5 6
Выходные данные #1
2 4 5 6 5
Входные данные #2
8 8 1 2 1 3 2 3 3 4 1 5 1 6 6 7 6 8
Выходные данные #2
3 1 5 1 6 3 4