Двенашки
Игра "двенашки" похожа на известную игру "пятнадцать". Она состоит из коробочки размером 5 строк на 3 столбца и двенадцати фишек, по размеру равных клетке коробочки и занумерованных числами от 1 до 12. Две клетки коробочки - вторая и четвертая в среднем столбце - имеют выступы и в них не могут находится фишки, в каждой из 13 оставшихся клеток может находится не более одной фишки. Таким образом, если все фишки находятся в коробке, то остается еще и пустая клетка. Ходом в игре является перемещение одной фишки на соседнюю клетку, которая до хода была пустой. Например, сдвинув из позиции на рис. 2 фишку 11 вверх, потом 10 вверх и 9 влево, получим позицию на рис. 1.
Ваша задача для данной начальной позиции определить кратчайшую последовательность ходов, приводящую к позиции, изображенной на рис. 1.
Входные данные
В первой строке входного файла находятся три числа - номера фишек, расположеных в первом ряду исходной позиции. Во второй строке находятся два числа, задающие номера фишек во втором ряду. В третьей, четвертой и пятой строках входного файла находятся соответственно три, два и три числа - номера фишек в соответствующих рядах. Отсутствие фишки обозначается номером 0.
Выходные данные
В первой строке выходного файла должно находится одно число K - число ходов в кратчайшем решении либо -1, если решения нет или оно требует более 70 ходов. В случае, когда существует решение не более, чем за 70 ходов, во второй строке файла должны находиться K символов, задающих последовательность ходов в решении следующим образом:
символ 'U' - двигается фишка, расположенная сверху от пустой клетки.
символ 'D' - двигается фишка, расположенная снизу от пустой клетки.
символ 'L' - двигается фишка, расположенная слева от пустой клетки.
символ 'R' - двигается фишка, расположенная справа от пустой клетки.