옥수수 미로

남부 온타리오의 옥수수 농장에서는 곡식을 거둔 뒤 가을에 옥수수 줄기 미로를 만든다.

밭은 직사각형 격자로 나타내고, 각 칸은 다음 중 하나이다.

• #: 서 있는 옥수수 줄기. 지나갈 수 없다.
• X: 나무나 건물처럼 밟아 길로 만들 수 없는 장애물. 지나갈 수 없다.
• .: 줄기를 밟아 만든 길. 지나갈 수 있다.

가장자리에 있는 길 칸은 정확히 하나이며, 그 칸이 입구이다. 나머지 길 칸은 모두 내부이다.

잭은 변을 공유하는 길 칸으로만 이동한다. 대각선으로는 이동하지 않는다.

입구에서 최단 거리로 가장 멀리 떨어진 길 칸이 미로의 중심이다. 거리는 입구와 중심을 포함해 경로가 지나는 길 칸의 수이다. 최단 거리가 최대인 칸이 여러 개여도 그 거리는 같다.

입구에서 중심까지 최단 경로의 길이를 구하시오.

다음 격자는 완성된 미로이다. 입구는 첫 행에 있는 유일한 길 칸이다.

#.X#######
#.#X#...##
#...X#.X.#
#.#......#
#.XXXX##.#
##########

입구를 E, 한 중심을 C, 그 경로의 나머지 칸을 +로 표시하면 아래와 같다. 이 경로의 길이는 12이다.

#EX#######
#+#X#C+.##
#+++X#+X.#
#.#++++..#
#.XXXX##.#
##########

첫째 줄에 행의 수 $N$과 열의 수 $M$이 주어진다.

다음 $N$개 줄에 길이가 $M$인 문자열이 주어진다. 각 문자는 #, X, . 중 하나이다.

가장자리의 .은 정확히 하나이다. 모든 .은 입구에서 도달할 수 있다.

입구에서 중심까지 최단 경로의 길이를 한 줄에 출력한다.

• $1 \le N, M \le 200$
• 격자의 각 칸은 #, X, . 중 하나이다.
• 가장자리에 있는 .은 정확히 하나이다.
• 모든 .은 입구에서 도달할 수 있다.