В городе проблемы с движением. Большинство людей отказываются ходить пешком, предпочитая ездить на авто. Проблема в том, что улочки узкие, а авто - широкие. Если два авто двигаются в противоположных направлениях, то на одной улице они образуют пробку. Поэтому все улицы решено сделать с односторонним движением. Однако имеется недостаточно дорожных знаков. Поэтому требуется Ваша помощь.
Вам дается карта города, описанная как планарный граф. Вы должны определить направления всех улиц, помня об ограничении: Из каждой вершины может исходить не более трех дуг (число входящих дуг не ограничено). Вам не требуется беспокоиться о других аспектах (например достижимости вершин или сильной связности). Если существует несколько решений, Вы можете выводить любое из них.
Первая строка ввода содержит два целых числа N и M (1 ≤ N ≤ 200000, 1 ≤ M ≤ 1000000), где N представляет количество вершин, а M - количество ребер. Следующие M строк описывают ребра. Каждое ребро описывается номерами двух смежных вершин i и j (1 ≤ i, j ≤ N). Гарантируется планарность графа, то есть, возможность нарисовать его на плоскости (вершины - точки, ребра - отрезки) таким образом, что никакие два отрезка не пересекаются (кроме общих вершин). В этом графе нет петель и нет множественных ребер.
Результаты выводятся в том же формате, что и на вводе. Только на этот раз ребра ориентированные (i, j означает ребро из i в j). Если для данного графа решения не существует, выводите строку no в вывод.