시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 20 8 8 50.000%

문제

육각 퍼즐이란 정육각형의 꼭지점과 중심에 원이 그려져 있는 퍼즐이고, 아래 그림과 같이 원이 연결되어 있다. 또, A, B, C, D, E, F로 글자가 새겨져 있는 동전이 아래 그림과 같이 원 위에 놓여 있다. 퍼즐에서 한 번 움직일 때, 동전을 연결된 빈 칸으로 움직일 수 있다.

처음 동전이 섞인 상태로 주어졌을 때, 동전을 아래 그림과 같이 맞추는 최소 이동 회수를 구하는 프로그램을 작성하시오. 처음 상태에서 가운데 칸은 비어있다.

처음 중심 정점은 비어있고 바깥쪽 정점 6 개가 A부터 F의 주어진 순열이 주어졌을 때 원래 ABCDEF 순서로 돌아가게 퍼즐을 푸려고 한다.

퍼즐의 상태는 위의 그림의 A 위치에 있는 동전부터 F까지 차례대로 주어진다. 퍼즐을 움직인 방법을 출력할 때는, 움직인 동전을 출력하면 된다.

예를 들어, FACDBE 퍼즐을 풀 때는 BEFAB로 움직이면 풀 수 있다.

퍼즐의 초기 상태가 주어졌을 때, 이 퍼즐을 푸는 방법을 출력하는 프로그램을 작성하시오. 이 때, 움직인 동전의 수를 최소로 해야 한다.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 퍼즐의 초기 상태가 주어진다.

출력

각 테스트 케이스에 대해서 최소 회수를 출력하고 공백을 출력한 뒤, 푸는 방법을 출력한다. 만약, 풀 수 없는 퍼즐이라면 -1을 출력한다.

예제 입력

12
FACDBE
ABCDEF
ADCEFB
ADCEBF
FEDCBA
FEDCAB
ECBFAD
ECBFDA
DCEBFA
DCEBAF
CBEADF
BDEAFC

예제 출력

5 BEFAB
0 
19 DABFECABFEDBACDEFAB
-1
29 EDCBEDFAEDFAEDBCAFBDEFACDEFAB
-1
19 CBFACBFACDEFACDEFAB
-1
13 CDAFBEDCBEDCB
-1
21 DAEBDAEBDCFEBDCABEFAB
16 FAEDBCAFBCAFEDCB

힌트