문제 설명

멋 부리기를 좋아하는 비타로는 카펫을 새로 장만했다. 카펫은 세로 $H$행, 가로 $W$열의 격자 모양으로 나누어진 직사각형 형태를 하고 있으며, 각 칸은 흰색이나 검은색 중 한 가지 색으로 칠해져 있다. 카펫의 위에서부터 $i$번째 행, 왼쪽에서부터 $j$번째 열 ($1 \le i \le H$, $1 \le j \le W$)에 있는 칸의 색은 문자열 $S_i$의 $j$번째 문자가 .일 때 흰색, #일 때 검은색이다.

비타로는 카펫의 가장 왼쪽 위 칸에 말을 놓고, 다음 조작을 몇 번 수행하여 그 말을 카펫의 가장 오른쪽 아래 칸에 도달하게 하는 놀이를 생각해 냈다.

• 말이 놓여 있는 칸과 색이 다르고, 상하좌우로 인접한 칸을 $1$개 골라 그 칸으로 말을 이동시킨다.

비타로는 도달할 때까지의 조작 횟수를 가능한 한 적게 하고 싶다. 단, 카펫의 무늬에 따라서는 도달하게 하지 못할 수도 있다.

카펫 무늬의 정보가 주어졌을 때, 조작을 반복하여 왼쪽 위 칸에서 오른쪽 아래 칸으로 말을 도달하게 하는 것이 가능한지 판정하고, 가능하다면 조작 횟수의 최솟값을 구하는 프로그램을 작성하시오.

제약 조건

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$는 길이 $W$인 문자열이다 ($1 \le i \le H$).
• $S_i$의 각 문자는 . 또는 #이다 ($1 \le i \le H$).
• $H, W$는 정수이다.

서브태스크

1. ($4$점) $H = 1$.
2. ($14$점) $H \le 5$, $W \le 5$.
3. ($24$점) $H \le 30$, $W \le 30$.
4. ($58$점) 추가 제약 조건이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.

H W
S_1
S_2
:
S_H

출력

조작을 반복하여 왼쪽 위 칸에서 오른쪽 아래 칸으로 말을 도달하게 하는 것이 가능한 경우에는 조작 횟수의 최솟값을, 불가능한 경우에는 -1을 표준 출력에 $1$줄로 출력하시오.

입출력 예

입력 예 1

4 5
...#.
#####
...#.
#.###

출력 예 1

9

예를 들어 그림과 같은 조작을 생각할 수 있다.

왼쪽 예에서는 $9$번의 조작으로, 오른쪽 예에서는 $13$번의 조작으로 왼쪽 위 칸에서 오른쪽 아래 칸으로 말을 도달하게 하는 것이 가능하다.

$9$번보다 적은 조작 횟수로 도달하게 하는 것은 불가능하므로 $9$를 출력한다.

이 입력 예는 서브태스크 $2, 3, 4$의 제약 조건을 만족한다.

입력 예 2

3 3
...
...
...

출력 예 2

-1

처음부터 조작을 할 수 없는 경우도 있다. 이 경우 말을 오른쪽 아래 칸에 도달하게 하는 것은 불가능하므로 -1을 출력한다.

이 입력 예는 서브태스크 $2, 3, 4$의 제약 조건을 만족한다.

입력 예 3

1 5
.#.#.

출력 예 3

4

이 입력 예는 모든 서브태스크의 제약 조건을 만족한다.

입력 예 4

5 5
###.#
.#...
.#..#
.####
##..#

출력 예 4

12

이 입력 예는 서브태스크 $2, 3, 4$의 제약 조건을 만족한다.

입력 예 5

7 5
.#.##
##...
.#.##
.###.
##.#.
...#.
##.#.

출력 예 5

12

이 입력 예는 서브태스크 $3, 4$의 제약 조건을 만족한다.