Theta Puzzle
Головоломка Тета представляет собой основание с 6 позициями на вершинах правильного шестиугольника и одной позицией в центре, соединенных, как показано на рисунке ниже. В игре участвуют шесть фишек, обозначенных буквами A, B, C, D, E и F. Один ход в головоломке заключается в перемещении фишки на соседнюю пустую позицию (по разрешенному соединению — отрезкам на диаграмме ниже). Цель игры — начать с начальной расстановки фишек с пустым центром и, выполняя последовательность ходов, достичь конфигурации, показанной на рисунке ниже.
Начальная позиция головоломки задается перестановкой букв от A до F. Первая буква соответствует позиции A на рисунке, следующая — позиции B и так далее.
Последовательность ходов задается перечислением меток фишек, которые необходимо переместить, в порядке их перемещения.
Например, чтобы решить головоломку с начальной расстановкой FACDBE, используйте ходы BEFAB.
Примечание: Не все начальные перестановки могут быть решены.
Напишите программу, которая, получив начальную перестановку, либо находит кратчайшую последовательность ходов для решения головоломки, либо определяет, что решения нет.
Входные данные
Первая строка ввода содержит одно целое число P, (1 ≤ P ≤ 1000), которое указывает количество наборов данных, следующих далее. Каждый набор данных — это одна строка, содержащая номер набора данных, за которым следует пробел, а затем перестановка букв от A до F, задающая начальную позицию головоломки.
Выходные данные
Для каждого набора данных выводится одна строка. Если решения нет, строка содержит десятичное число, указывающее номер набора данных, за которым следует пробел, а затем строка NO SOLUTION. Если решение есть, строка содержит десятичное число, указывающее номер набора данных, за которым следует пробел, затем количество ходов в решении, за которым следует пробел, а затем решение в виде строки из букв A до F. Если количество ходов равно нулю (0), вы все равно должны вывести пробел после 0, даже если строки букв нет.