정육면체 8퍼즐

3×3 보드 위에 정육면체 주사위 8개가 놓여 있고, 아홉 칸 중 정확히 한 칸은 비어 있다.

각 주사위는 마주 보는 두 면이 같은 색이 되도록 칠해져 있으며, 세 쌍의 면은 파랑, 하양, 빨강 세 가지 색을 하나씩 사용한다. 여덟 개의 주사위는 모두 같은 방향으로 시작한다. 윗면(과 아랫면)은 하양이고, 보드의 위·아래 방향(북·남)을 향한 두 면은 빨강, 보드의 좌·우 방향(동·서)을 향한 두 면은 파랑이다.

주사위는 상하좌우로 인접한 칸이 비어 있을 때에만 그 칸으로 굴릴 수 있다. 90도 굴리면 주사위가 빈 칸으로 넘어가고, 원래 있던 칸이 새로운 빈 칸이 된다. 북쪽이나 남쪽으로 굴리면 윗면의 색과 북·남면의 색이 서로 바뀌고, 동쪽이나 서쪽으로 굴리면 윗면의 색과 동·서면의 색이 서로 바뀐다.

모든 주사위의 윗면 색이 주어진 목표 색과 같아지고 빈 칸이 목표 위치에 오면 퍼즐이 풀린 것이다.

처음에 비어 있는 칸과 목표 색이 주어질 때, 퍼즐을 푸는 데 필요한 최소 굴림 횟수를 출력하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 처음에 비어 있는 칸의 좌표가 주어지는데, 왼쪽에서부터 센 열 번호(13)와 위에서부터 센 행 번호(13)가 순서대로 주어진다. 다음 세 줄에는 목표 보드가 맨 위 행부터 한 줄에 세 개씩, 공백으로 구분되어 주어진다. 각 기호는 B(파랑), W(하양), R(빨강), E 중 하나이며, E는 풀린 상태에서 비어 있어야 하는 칸을 나타내고 정확히 한 번만 나온다.

입력의 끝은 "0 0"만 있는 줄이다. 테스트 케이스는 16개보다 적다.

각 테스트 케이스마다 퍼즐을 푸는 데 필요한 최소 굴림 횟수를 한 줄에 하나씩 출력한다. 이 값이 30을 넘거나 퍼즐을 풀 수 없으면 -1을 출력한다.