eolymp
bolt
Try our new interface for solving problems
Problems

Городок

Городок

Time limit 2 seconds
Memory limit 64 MiB

В городе проблемы с движением. Большинство людей отказываются ходить пешком, предпочитая ездить на авто. Проблема в том, что улочки узкие, а авто - широкие. Если два авто двигаются в противоположных направлениях, то на одной улице они образуют пробку. Поэтому все улицы решено сделать с односторонним движением. Однако имеется недостаточно дорожных знаков. Поэтому требуется Ваша помощь.

Вам дается карта города, описанная как планарный граф. Вы должны определить направления всех улиц, помня об ограничении: Из каждой вершины может исходить не более трех дуг (число входящих дуг не ограничено). Вам не требуется беспокоиться о других аспектах (например достижимости вершин или сильной связности). Если существует несколько решений, Вы можете выводить любое из них.

Input data

Первая строка ввода содержит два целых числа N и M (1N200000, 1M1000000), где N представляет количество вершин, а M - количество ребер. Следующие M строк описывают ребра. Каждое ребро описывается номерами двух смежных вершин i и j (1i, jN). Гарантируется планарность графа, то есть, возможность нарисовать его на плоскости (вершины - точки, ребра - отрезки) таким образом, что никакие два отрезка не пересекаются (кроме общих вершин). В этом графе нет петель и нет множественных ребер.

Output data

Результаты выводятся в том же формате, что и на вводе. Только на этот раз ребра ориентированные (i, j означает ребро из i в j). Если для данного графа решения не существует, выводите строку no в вывод.

Examples

Input example #1
7 11
1 4
1 6
2 3
3 4
5 1
5 2
5 3
5 4
5 6
5 7
6 7
Output example #1
7 11
1 6
1 4
2 3
3 4
4 5
5 3
5 2
5 1
6 7
6 5
7 5