Джилл і Філові Паломницькі Подорожі
Джилл і її друг Філ вирішили покататися на велосипедах по Варшаві, щоб відчути себе туристами та оглянути визначні місця. Оскільки вони не знайомі з містом, вони хочуть обрати маршрути, які легко запам'ятати. На кожному перехресті, яке вони зустрінуть, є рівно чотири дороги, що ведуть у різні напрямки: північ, схід, південь і захід. Вони залишатимуть перехрестя, обираючи дорогу, яка знаходиться відносно ліворуч (L), праворуч (R) або прямо (F) від тієї, якою вони в'їхали на перехрестя (ця дорога також розташована на одній з чотирьох точок компаса). Вони не пройдуть через жодне перехрестя більше двох разів. Послідовність літер (F, L, R), що описує їхній маршрут, є паліндромом!
Наприклад, розглянемо карту, зображену праворуч, де північ знаходиться вгорі. Кожне пронумероване коло представляє перехрестя; кожне має чотири дороги, хоча деякі можуть бути тупиками, як дорога на схід від перехрестя 3. Коло, позначене "x", — це готель Джилл і Філа, звідки починаються всі їхні маршрути, рухаючись прямо. Лінії (ребра) між колами представляють дороги.
Один з паліндромних маршрутів від готелю може бути FLRLF: прямо до 3, потім ліворуч до 2, праворуч до 1, ліворуч до 3, і нарешті прямо до готелю. Цей маршрут показано на карті направленими ребрами. Інший паліндромний маршрут — FLLFFLLF. Він проходить від готелю до перехресть 3, 2, 4, знову 4, 2, 1, 3, і повертається до готелю.
Дано карту, знайдіть усі паліндромні маршрути, які можуть обрати Джилл і Філ.
Вхідні дані
Вхід містить кілька карт, після яких слідує рядок з одним нулем.
Перший рядок для кожної карти вказує кількість перехресть, N, яка не перевищує 15. Рядок містить номер перехрестя (1..N), за яким слідує велика літера точки компаса ('N', 'E', 'S', або 'W'), що вказує напрямок дороги Прямо від готелю.
Далі йдуть N рядків, по одному для кожного перехрестя (пронумеровані від 1 до N). Чотири поля, розділені пробілами, на K–му з цих рядків вказують перехрестя, до яких підключені чотири дороги від перехрестя K; поля відповідають дорогам, що виходять на північ, схід, південь і захід від перехрестя K, відповідно. Кожне поле містить одне з наступного:
номер перехрестя L, за яким одразу йде одна з великих літер точки компаса 'N', 'E', 'S', або 'W'; це вказує, що відповідна дорога, що виходить з перехрестя K, з'єднується з перехрестям L у вказаній точці компаса.
0; це вказує, що відповідна дорога є тупиком, по якому подорожувати неможливо.
–1; це позначає дорогу, яка веде до готелю. На карті буде лише одна така дорога.
Вихідні дані
Для кожної карти виведіть номер карти та всі можливі паліндромні маршрути в лексикографічному порядку. Виведіть повідомлення "NO ROUTES", якщо жодного паліндромного маршруту знайти неможливо. Дотримуйтесь формату зразка виводу.