Совет Вашего родного города решил улучшить размещение дорожных знаков, особенно в тупиках. Они дали Вам дорожную карту, и Вы должны определить, где поставить знаки чтобы обозначить тупики. Они хотят, чтобы Вы использовали как можно меньше знаков.
Дорожная карта представляет собой набор перекрестков, соединенных улицами с двусторонним движением. Следующее правило описывает, как получить полное размещение знаков тупика. Рассмотрим улицу , соединяющую место с другим местом. -вход в становится тупиковым, если после входа в из невозможно вернуться в не делая разворот. Разворот --- это поворот на градусов, сразу же меняющий направление.
Для экономии затрат Вы решили не устанавливать лишние тупиковые знаки, как указано в следующем правиле. Рассмотрим улицу со знаком тупика на -въезде и другую улицу со знаком тупика на -въезде. Если после въезда в из можно достигнуть и въехать в , не делая разворота, то знак тупика на -вход улицы является избыточным. См. примеры на рисунке E.1.
\includegraphics{https://static.eolymp.com/content/1q/1qspidde3d4u15asushgof2b60.gif}
Рисунок E.1: Иллюстрация входных данных из примером с указанием места размещения неизбыточных знаков тупика.
\InputFileПервая строка содержит два целых числа и , где --- количество перекрестков, а --- количество улиц. Каждая из следующих строк содержит два целых числа и , обозначающих что улица с двусторонним движением соединяет перекрестки и . Все улицы во входных данных различны.
\OutputFileВ первой строке выведите количество установленных тупиковых знаков. В каждой из следующих строк выведите два целых числа и , обозначающие что на въезде на улицу, соединяющую перекрестки и , необходимо установить знак тупика. Строки, описывающие тупиковые знаки, должны быть отсортированы в порядке возрастания , а при равных значениях --- в порядке возрастания .
\includegraphics{https://static.eolymp.com/content/98/98o8dfl2hh2c1fdpldt758pb94.gif}