포탈

첼은 글라도스가 새로 낸 퍼즐을 풀어야 한다. 첼이 있는 방은 $N$행 $M$열 행렬로 나타낼 수 있고, 각 칸은 다음 넷 중 하나다.

• 벽이 있는 칸, #로 표시한다.
• 첼이 처음 서 있는 칸, C로 표시한다.
• 첼이 도착해야 하는 칸, F로 표시한다.
• 빈 칸, .로 표시한다.

첼은 벽에 포탈을 만드는 포탈 건을 들고 있다. 한 번의 행동으로 다음 중 하나를 한다.

1. 위, 아래, 왼쪽, 오른쪽으로 인접한 칸에 이동한다. 벽이 있는 칸으로는 이동할 수 없다. 이 행동에는 시간이 1 걸린다.
2. 위, 아래, 왼쪽, 오른쪽 중 한 방향으로 몸을 돌려 총을 쏜다. 총알은 그 방향으로 날아가 처음 만나는 벽에 맞고, 포탈은 총알이 맞은 쪽 면에만 생긴다. 벽이 인접해 있지 않아도 쏠 수 있다. 포탈은 동시에 두 개까지만 남는다. 이미 두 개가 있을 때 새 포탈을 만들면 먼저 만든 포탈이 사라진다. 이미 포탈이 있는 면에는 새 포탈을 만들 수 없다. 이 행동에는 시간이 걸리지 않는다. 즉 0이다.
3. 벽과 인접한 칸에 서 있고 그 벽의 자기 쪽 면에 포탈이 있으면, 그 포탈로 들어가 다른 포탈과 맞닿은 빈 칸으로 나올 수 있다. 포탈이 두 개 다 있을 때만 할 수 있고, 시간이 1 걸린다.

한 번 만든 포탈은 사라지기 전까지 그 자리에 남는다. 첼이 움직여도 포탈은 그대로다. 벽 한 칸에는 면이 넷 있으므로, 면이 서로 다르면 같은 벽 칸에 포탈 두 개가 함께 있을 수 있다.

첼이 퍼즐을 푸는 데, 즉 F 칸에 도착하는 데 걸리는 최소 시간을 구하라.

방의 가장자리는 항상 벽이고, C와 F는 각각 한 번씩만 나온다.

첫째 줄에 양의 정수 $N$과 $M$이 주어진다. ($4 \le N, M \le 500$)

다음 $N$개 줄에는 방의 모양을 나타내는 문자가 $M$개씩 주어진다.

퍼즐을 푸는 데 걸리는 최소 시간을 출력한다. 풀 수 없으면 nemoguce를 출력한다. 따옴표는 쓰지 않으며, 크로아티아어로 불가능을 뜻한다.

두 번째 예제는 행동 8번으로 풀 수 있다. 칸의 위치는 (행, 열)로 쓴다.

1. 왼쪽으로 돌아 총을 쏜다. (3,1)에 있는 벽의 오른쪽 면에 포탈이 생긴다.
2. 아래쪽으로 총을 쏜다. (6,2)에 있는 벽의 위쪽 면에 포탈이 생긴다.
3. (3,1)의 포탈로 들어가 (5,2)로 나온다.
4. 오른쪽으로 돌아 총을 쏜다. (5,7)에 있는 벽의 왼쪽 면에 포탈이 생긴다. 포탈이 이미 두 개였으므로 (3,1)의 포탈이 사라진다.
5. (6,2)의 포탈로 들어가 (5,6)으로 나온다.
6. 위쪽으로 총을 쏜다. (1,6)에 있는 벽의 아래쪽 면에 포탈이 생기고, (6,2)의 포탈이 사라진다.
7. (5,7)의 포탈로 들어가 (2,6)으로 나온다.
8. 오른쪽으로 한 칸 이동해 퍼즐을 푼다.

1, 2, 4, 6번 행동은 시간이 0이고 나머지 네 번은 각각 시간이 1이므로, 전체 시간은 4다.