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

Дорожная карта представляет собой набор перекрестков, соединенных улицами с двусторонним движением. Следующее правило описывает, как получить полное размещение знаков тупика. Рассмотрим улицу $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}