Совет Вашего родного города решил улучшить размещение дорожных знаков, особенно в тупиках. Они дали Вам дорожную карту, и Вы должны определить, где поставить знаки чтобы обозначить тупики. Они хотят, чтобы Вы использовали как можно меньше знаков.
Дорожная карта представляет собой набор перекрестков, соединенных улицами с двусторонним движением. Следующее правило описывает, как получить полное размещение знаков тупика. Рассмотрим улицу , соединяющую место с другим местом. -вход в становится тупиковым, если после входа в из невозможно вернуться в не делая разворот. Разворот — это поворот на градусов, сразу же меняющий направление.
Для экономии затрат Вы решили не устанавливать лишние тупиковые знаки, как указано в следующем правиле. Рассмотрим улицу со знаком тупика на -въезде и другую улицу со знаком тупика на -въезде. Если после въезда в из можно достигнуть и въехать в , не делая разворота, то знак тупика на -вход улицы является избыточным. См. примеры на рисунке E.1.
Рисунок E.1: Иллюстрация входных данных из примером с указанием места размещения неизбыточных знаков тупика.
Первая строка содержит два целых числа и , где — количество перекрестков, а — количество улиц. Каждая из следующих строк содержит два целых числа и , обозначающих что улица с двусторонним движением соединяет перекрестки и . Все улицы во входных данных различны.
В первой строке выведите количество установленных тупиковых знаков. В каждой из следующих строк выведите два целых числа и , обозначающие что на въезде на улицу, соединяющую перекрестки и , необходимо установить знак тупика. Строки, описывающие тупиковые знаки, должны быть отсортированы в порядке возрастания , а при равных значениях — в порядке возрастания .