SP7583 YOKOC - Cubic Eight-Puzzle

Let's play a puzzle using eight cubes placed on a 3 x 3 board leaving one empty square. Faces of cubes are painted with three colors. As a puzzle step, you can roll one of the cubes to the adjacent empty square. Your goal is to make the specified color pattern visible from above by a number of such steps. The rules of this puzzle are as follows. 1. **Coloring of Cubes:** All the cubes are colored in the same way as shown in Figure 3. The opposite faces have the same color. 

The input is a sequence of datasets. The end of the input is indicated by a line containing two zeros separated by a space. The number of datasets is less than 16. Each dataset is formatted as follows. > _x_ _y_ _F_ $ _{11} $ _F_ $ _{21} $ _F_ $ _{31} $ _F_ $ _{12} $ _F_ $ _{22} $ _F_ $ _{32} $ _F_ $ _{13} $ _F_ $ _{23} $ _F_ $ _{33} $ The first line contains two integers _x_ and _y_ separated by a space, indicating the position (_x_, _y_) of the initially empty square. The values of _x_ and _y_ are 1, 2, or 3. The following three lines specify the color pattern to make. Each line contains three characters _F_ $ _{1j} $ , _F_ $ _{2j} $ , and _F_ $ _{3j} $ , separated by a space. Character _F_ $ _{ij} $ indicates the top color of the cube, if any, at position (_i_, _j_) as follows: B: Blue, W: White, R: Red, E: the square is Empty. There is exactly one `E' character in each dataset.

For each dataset, output the minimum number of steps to achieve the goal, when the goal can be reached within 30 steps. Otherwise, output ``-1'' for the dataset.