Hexagonal Puzzle

A hexagonal board has six outer cells and one center cell. The outer cells are named A, B, C, D, E, and F in the same order used by the input. Initially the center cell is empty, and the six coins labeled A through F occupy the outer cells.

In one move, choose a coin in a cell connected to the empty cell and move that coin into the empty cell. The cell connections are:

• outer cycle: A-B, B-C, C-D, D-E, E-F, F-A
• center cell: connected to B and E

The goal state has coins A, B, C, D, E, and F in outer cells A through F respectively, with the center cell empty.

Given an initial state, find the minimum number of moves needed to reach the goal and one sequence of coins moved in such an optimal solution. If the goal cannot be reached, report that it is impossible.

The first line contains the number of test cases T (1 <= T <= 1000). Each of the next T lines contains one initial state: a length-6 permutation of A through F, listed from outer cell A through outer cell F. The center cell is initially empty.

For each test case, print one line. If the puzzle can be solved, print the minimum move count, one space, and the sequence of moved coin labels. The sequence may be empty when the move count is 0. If the puzzle cannot be solved, print -1.