Совет Вашего родного города решил улучшить размещение дорожных знаков, особенно в тупиках. Они дали Вам дорожную карту, и Вы должны определить, где поставить знаки чтобы обозначить тупики. Они хотят, чтобы Вы использовали как можно меньше знаков.
Дорожная карта представляет собой набор перекрестков, соединенных улицами с двусторонним движением. Следующее правило описывает, как получить полное размещение знаков тупика. Рассмотрим улицу S, соединяющую место x с другим местом. x-вход в S становится тупиковым, если после входа в S из x невозможно вернуться в x не делая разворот. Разворот — это поворот на 180 градусов, сразу же меняющий направление.
Для экономии затрат Вы решили не устанавливать лишние тупиковые знаки, как указано в следующем правиле. Рассмотрим улицу S со знаком тупика на x-въезде и другую улицу T со знаком тупика на y-въезде. Если после въезда в S из x можно достигнуть y и въехать в T, не делая разворота, то знак тупика на y-вход улицы T является избыточным. См. примеры на рисунке E.1.
Рисунок E.1: Иллюстрация входных данных из примером с указанием места размещения неизбыточных знаков тупика.
Первая строка содержит два целых числа n и m, где n (1≤n≤5⋅105) — количество перекрестков, а m (0≤m≤5⋅105) — количество улиц. Каждая из следующих m строк содержит два целых числа v и w (1≤v<w≤n), обозначающих что улица с двусторонним движением соединяет перекрестки v и w. Все улицы во входных данных различны.
В первой строке выведите количество k установленных тупиковых знаков. В каждой из следующих k строк выведите два целых числа v и w, обозначающие что на въезде v на улицу, соединяющую перекрестки v и w, необходимо установить знак тупика. Строки, описывающие тупиковые знаки, должны быть отсортированы в порядке возрастания v, а при равных значениях — в порядке возрастания w.