Магічний Лабіринт
Є магічний лабіринт, у якому мешкають дуже страшні монстри. Лабіринт розділений на квадрати, кожен з яких може бути або вільним, або містити перешкоду. Вільні квадрати поділяються на небезпечні та безпечні. Ваша мета — почати з будь-якого вільного квадрата і, рухаючись лише через вільні квадрати, якнайшвидше дістатися до безпечного квадрата. Кожен ваш хід позначається як "U", "D", "L", "R", що означає рух вгору, вниз, вліво та вправо відповідно.
Якщо ви намагаєтеся рухатися в перешкоду або за межі лабіринту, ваше положення не змінюється. Так само, якщо ви вже досягли безпечного квадрата, ви залишаєтеся на місці і не можете його покинути.
Ви добре знаєте структуру лабіринту, але, на жаль, не знаєте, з якої позиції ви починаєте. Знайдіть найкоротшу послідовність ходів, яка приведе вас до безпечного квадрата, незалежно від вашої початкової позиції.
Вхідні дані
Перша строка вхідних даних містить два цілі числа M та N, що визначають кількість рядків та стовпців у лабіринті відповідно (1 ≤ M, N ≤ 5). Кожен з наступних M рядків містить рядок довжиною N, що складається з символів "." (вільний небезпечний квадрат), "*" (вільний безпечний квадрат) або "#" (перешкода). Ці рядки визначають карту лабіринту.
Вихідні дані
Виведіть один рядок, що містить найкоротшу послідовність ходів, яка приведе до безпечного квадрата. Якщо існує декілька найкоротших послідовностей, виведіть ту, яка є лексикографічно найменшою. Якщо немає жодного можливого рішення, виведіть "NO SOLUTION".