Містечко#5476
У місті проблеми з рухом. Більшість людей відмовляється ходити пішки, віддає перевагу їзді на авто. Проблема у тому, що вулички вузькі, а авто — широкі. Якщо два авто рухаються у протилежних напрямках, то на одній вулиці вони створюють пробку. Тому усі вулиці вирішено зробити з одностороннім рухом. Проте у наявності недостатньо дорожніх знаків. Тому потрібна Ваша допомога.
Вам задано карту міста, описану як планарний граф. Ви повинні визначити напрямки усіх вулиць, пам'ятаючи про обмеження: з кожної вершини може виходити не більше трьох дуг (число дуг, які входять, не обмежено). Вам не потрібно турбуватися про інші аспекти (наприклад, досяжність вершин чи сильну зв'язність). Якщо існує декілька розв'язків, Ви можете виводити довільний з них.
Перший рядок входу містить два цілих числа та (1 \leq N \leq 200\,000, 1 \leq M \leq 1\,000\,000), де подає кількість вершин, а — кількість ребер. Наступні рядків описують ребра. Кожне ребро описується номерами двох суміжних вершин та (1 \leq i, j \leq N). Гарантується планарність графа, тобто можливість намалювати його на площині (вершини — точки, ребра — відрізки) таким чином, що ніякі два відрізки не перетинаються (крім спільних вершин). У цьому графі немає петель і немає кратних ребер.
Результати виводяться у тому ж форматі, що і на вході. Лише на цей раз ребра орієнтовані ( позначає ребро з в ). Якщо для заданого графа розв'язку не існує, виведіть рядок no у вихід.
Приклад 1