Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Forum Home ProblemSet Status Ranklist 1 Contest LoginRegister Exam
2019级ACM集训队预报名 Problem 1792. -- Theta Puzzle

Theta Puzzle

Time Limit: 1 Sec  Memory Limit: 64 MB  Special Judge
Submit: 22  Solved: 4
[Submit][Status][Forum]

Description

The Theta Puzzle consists of a base with 6 positions at the vertices of a regular hexagon and another position at the center, connected as shown in the figure below. There are six tokens labeled A, B, C, D, E and F. A single move of the puzzle is to move a token to an adjacent empty position (along an allowed connection – the line segments in the diagram below). The idea of the puzzle is to start with an initial arrangement of tokens with the center empty and, by a sequence of moves, get to the configuration in the figure below.


An initial position for the puzzle is given by a permutation of the letters A through F. The first letter starts at A in the figure, the next at B and so on.
A sequence of moves is specified by listing the labels of tokens to be moved, in the order they are to be moved.
For example, to solve the puzzle FACDBE, use the moves BEFAB.

 


Note: Not all starting permutations can be solved.
Write a program which, given an initial permutation, either finds the shortest sequence of moves to solve the puzzle or determines that there is no solution.

Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. Each data set is a single line that contains the data set number, followed by a space, followed by a permutation of the letters A through F giving the initial puzzle position.

Output

For each data set there is a single line of output. If there is no solution, the line contains a decimal integer giving the data set number followed by a single space, followed by the string NO SOLUTION.
If there is a solution, the line contains a decimal integer giving the data set number followed by a single space, followed by the number of moves in the solution, followed by a single space, followed by the solution as a string of the letters A through F. If the number of moves is zero (0), you should still output the space after the 0, even though there is no string of letters.

Sample Input

12
1 FACDBE
2 ABCDEF
3 ADCEFB
4 ADCEBF
5 FEDCBA
6 FEDCAB
7 ECBFAD
8 ECBFDA
9 DCEBFA
10 DCEBAF
11 CBEADF
12 BDEAFC

Sample Output

1 5 BEFAB
2 0 
3 19 DABFECABFEDBACDEFAB
4 NO SOLUTION
5 29 BCDEBCAFBCAFBCEDFAECBAFDCBAFE
6 NO SOLUTION
7 19 CBFACBFACDEFACDEFAB
8 NO SOLUTION
9 13 CDAFBEDCBEDCB
10 NO SOLUTION
11 21 DAEBDAEBDCFEBDCABEFAB
12 16 FAEDBCAFBCAFEDCB

HINT

special judge


Source

2009 Greater New York Regional

[Submit][Status][Forum]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin