Дванашки#5303
Гра "дванашки" схожа на відому гру "п'ятнадцять". Вона складається з коробочки розміром рядків на стовбця і дванадцяти фішок, по розміру рівних клітинці коробочки і пронумерованих числами від до . Дві клітинки коробочки — друга і четверта у середньому стовбці — мають виступи і у них не можуть знаходитись фішки. У кожній з клітинок, що залишились, може знаходитись не більше однієї фішки. Таким чином, якщо усі фішки знаходяться у коробочці, то залишається ще й порожня клітинка. Ходом у грі є переміщення однієї фішки у сусідню клітинку, яка до ходу була порожньою. Наприклад, зсунувши з позиції на рис. 2 фішку вгору, потім вгору і ліворуч, отримаємо позицію на рис. 1.
Ваше завдання для заданої початкової позиції визначити найкоротшу послідовність ходів, які приводять до позиції, зображеної на рис. 1.
У першому рядку вхідного файлу знаходяться три числа — номери фішок, розміщених у першому ряду початкової позиції. У другому рядку знаходяться два числа, які задають номери фішок у другому ряду. У третьому, четвертому та п'ятому рядках вхідного файлу знаходяться відповідно три, два і три числа — номери фішок у відповідних рядах. Відсутність фішки позначається номером .
У першому рядку вихідного файлу повинно знаходитись одне число — кількість ходів у найкоротшому розв'язку або , якщо розв'язку немає або він вимагає більше ходів. У випадку, коли існує розв'язок не більше, ніж за ходів, у другому рядку файлу повинні знаходитись символів, які задають послідовність ходів у розв'язку наступним чином:
символ 'U' — пересувається фішка, розміщена зверху від порожньої клітинки.
символ 'D' — пересувається фішка, розміщена знизу від порожньої клітинки.
символ 'L' — пересувається фішка, розміщена ліворуч від порожньої клітинки.
символ 'R' — пересувається фішка, розміщена праворуч від порожньої клітинки.
Приклад 1