색칠된 정육면체

절대반지가 프로도의 손에 있다는 사실이 밝혀지자, 간달프는 자신이 속한 마법사단의 수장인 사루만에게 조언을 구하러 달려갔다. 사루만은 반지를 파괴해야 한다는 간달프의 생각에 동의하지 않았고, 간달프를 놓아주어 프로도를 돕게 할 수 없다고 여겨 그를 아이센가드의 검은 탑 꼭대기 방에 가두었다. 죄수를 붙잡아 두기 위해, 방에서 나가는 유일한 통로인 문은 오직 수수께끼를 풀어야만 열 수 있게 해 두었다.

방을 살피던 간달프는 탑의 지붕으로 통하는 듯한 문에서 기묘한 자물쇠를 발견했다. 그 자물쇠는 어느 면에도 표시가 없는 평범한 정육면체였고, $m \times n$ 크기의 격자 위에 놓여 있었다. 격자에서 정확히 여섯 칸에 물감이 칠해져 있었다.

정육면체는 한 번에 한 칸씩, 상하좌우 네 방향 중 하나로 굴러간다. 정육면체가 어떤 칸으로 굴러가면, 그 칸에 닿는 면(새로 바닥이 되는 면)만이 그 칸과 상호작용하며, 그 면과 그 칸에 칠해진 물감이 서로 교환된다.

• 바닥이 되는 면이 비어 있고 칸에 물감이 칠해져 있으면, 물감이 칸에서 면으로 옮겨져 칸은 비게 된다.
• 바닥이 되는 면에 물감이 칠해져 있고 칸이 비어 있으면, 물감이 면에서 칸으로 옮겨져 면은 비게 된다.
• 둘 다 칠해져 있거나 둘 다 비어 있으면 아무 변화도 일어나지 않는다.

지붕으로 통하는 문은, 어떤 이동 순서를 거쳐 정육면체가 여섯 면이 모두 칠해진 상태로 목표 칸에 도달할 때에만 열린다. 간달프는 이를 가능한 한 적은 이동 횟수로 해내야 한다.

물감의 초기 배치, 정육면체의 시작 칸, 목표 칸이 주어질 때, 정육면체를 여섯 면이 모두 칠해진 상태로 목표 칸에 옮기기 위해 필요한 최소 이동 횟수를 구하여라.

예를 들어 첫 번째 테스트 케이스에서, 열 번 이동하는 한 가지 최적 순서는 다음과 같다: 아래, 오른쪽, 오른쪽, 위, 오른쪽, 오른쪽, 아래, 왼쪽, 오른쪽, 왼쪽.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 문자로 이루어진 $m \times n$ 격자이며, $2 \le m, n \le 20$ 이다. 각 문자는 다음 중 하나이다.

• . — 빈 칸;
• P — 물감이 칠해진 칸;
• # — 정육면체가 절대 들어갈 수 없는 금지된 칸;
• C — 정육면체의 시작 칸;
• G — 목표 칸.

모든 테스트 케이스에는 P가 정확히 여섯 개, C가 정확히 하나, G가 정확히 하나 있으며, .은 최대 열두 개까지 있을 수 있다. 인접한 테스트 케이스는 한 줄의 빈 줄로 구분된다. 입력은 파일의 끝에서 종료된다.

각 테스트 케이스마다, 목표 상태에 도달하기 위한 최소 이동 횟수를 한 줄에 하나씩 출력한다. 목표 상태에 도달할 수 없으면 -1을 출력한다.