Quiz
Кожен з вас скоріше усього знайомий з дитячою грою "п'ятнашки". У цій задачі потрібно знайти розв'зок для деякої позиції.
Гра полягає у наступному: є квадратне поле N×N, розбите на клітинки 1×1. В усіх клітинках крім однієї є фішки, на кожній з яких записано число від 1 до N^2-1. Кожне число зустрічається рівно один раз. На цьому полі можна здійснювати ходи фішками, а саме, за один хід можна пересунути одну з сусідніх з вільним місцем фішок на це вільне місце. При цьому на місці фішки утворюється вільне місце. Фішки не можуть залишати межі поля.
Розв'чзати головоломку — значить розмістити фішки у певному порядку:
Вільне місце повинно опинитись у останній клітинці останнього рядка.
Для звичайних п'ятнашок це виглядає как:
Задано позицію, знайти послідовність ходів (не обов'язково найкоротшу, можливо порожню), яка її розв'язує. Або повідомити, що позиція не має розв'язку.
Вхідні дані
У першому рядку число N — розмір поля. Далі N рядків по N чисел у кожному Числа від 1 до N^2-1 відповідають фішкам, 0 відповідає вільному місцю. Кожне число від 0 до N^2-1 зустрічається рівно один раз.
Вихідні дані
Якщо позиція не має розв'язку, вивести "No". У протилежному випадку у першому рядку вивести "Yes", а у другому рядок з ходів (без пропусків):
'L' - означає, что на вільне місце потрібно перемістити фішку, яка знаходиться ліворуч від нього.
'R' - означає, что на вільне місце потрібно перемістити фішку, яка знаходиться праворуч від нього.
'U' - означає, что на вільне місце потрібно перемістити фішку, яка знаходиться зверху від нього.
'D' - означає, что на вільне місце потрібно перемістити фішку, яка знаходиться знизу від нього.
Кількість ходів не повинна перевищувати 2500000. Якщо розв'язків декілька, можете вивести довільний з них.
Обмеження
2 ≤ N ≤ 50
0 ≤ a_ij ≤ N^2-1