Головоломка Theta#2448
Головоломка Theta складається з основи з 6 позиціями на вершинах правильного шестикутника та ще однією позицією в центрі, з’єднаних, як показано на рисунку нижче. Є шість фішок, позначених літерами A, B, C, D, E та F. Один хід у головоломці — це переміщення фішки на сусідню порожню позицію (по дозволеному з’єднанню — відрізках на діаграмі нижче). Мета головоломки — почати з початкового розташування фішок із порожнім центром і, виконуючи послідовність ходів, досягти конфігурації, показаної на рисунку нижче.
Початкова позиція для головоломки задається перестановкою літер від A до F. Перша літера розміщується на позицію A на рисунку, наступна — на B, і так далі.
Послідовність ходів задається шляхом перелічення позначень фішок, які потрібно перемістити, у порядку їх переміщення.
Наприклад, щоб розв’язати головоломку FACDBE, використовуйте ходи BEFAB.
Примітка: Не всі початкові перестановки можна розв’язати.
Напишіть програму, яка для заданої початкової перестановки знаходить найкоротшу послідовність ходів для розв’язання головоломки або визначає, що розв’язку не існує.
У першому рядку міститься одне ціле число (1 \leq P \leq 1000) — кількість наборів даних. Кожен набір даних міститься в окремому рядку: номер набору, пробіл і перестановка літер від до , що задає початкову позицію головоломки.
Для кожного набору даних виведіть один рядок. Якщо розв’язку не існує, рядок повинен містити номер набору, пробіл і рядок NO SOLUTION. Якщо розв’язок існує, рядок повинен містити номер набору, пробіл, кількість ходів, пробіл та розв’язок у вигляді рядка з літер від до . Якщо кількість ходів дорівнює нулю (), виведіть пробіл після , навіть якщо немає рядка з літерами.
Приклад 1