Description

Bitaro, who loves fashion, bought a new carpet. The carpet has a rectangular shape divided into a grid of $H$ rows vertically and $W$ columns horizontally, and each cell is painted either white or black. The color of the cell at the $i$-th row from the top and $j$-th column from the left ($1 \le i \le H$, $1 \le j \le W$) of the carpet is white when the $j$-th character of the string $S_i$ is ., and black when it is #.

Bitaro came up with a game in which he places a piece on the top-leftmost cell of the carpet and makes the piece reach the bottom-rightmost cell of the carpet by performing the following operation some number of times:

• Choose $1$ cell that has a different color from the cell where the piece is currently placed and is vertically or horizontally adjacent to it, and move the piece to that cell.

Bitaro wants to minimize the number of operations required to reach the destination. However, depending on the pattern of the carpet, it might be impossible to make the piece reach the destination.

Given the information about the pattern of the carpet, write a program to determine whether it is possible to make the piece reach the bottom-rightmost cell from the top-leftmost cell by repeating the operation, and if possible, find the minimum number of operations.

Constraints

• $1 \le H \le 500$.
• $1 \le W \le 500$.
• $(H, W) \neq (1, 1)$.
• $S_i$ is a string of length $W$ ($1 \le i \le H$).
• Each character of $S_i$ is . or # ($1 \le i \le H$).
• $H, W$ are integers.

Subtasks

1. ($4$ points) $H = 1$.
2. ($14$ points) $H \le 5$, $W \le 5$.
3. ($24$ points) $H \le 30$, $W \le 30$.
4. ($58$ points) No additional constraints.

Input

The input is given from standard input in the following format:

H W
S_1
S_2
:
S_H

Output

If it is possible to make the piece reach the bottom-rightmost cell from the top-leftmost cell by repeating the operation, output the minimum number of operations; if it is impossible, output -1, in $1$ line to standard output.

Sample I/O

Sample Input 1

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

Sample Output 1

9

For example, the operations shown in the figure can be considered.

It is possible to make the piece reach the bottom-rightmost cell from the top-leftmost cell in $9$ operations in the left example, and in $13$ operations in the right example.

Since it is impossible to reach it in fewer than $9$ operations, output $9$.

This sample input satisfies the constraints of Subtasks $2, 3, 4$.

Sample Input 2

3 3
...
...
...

Sample Output 2

-1

There are cases where no operation can be performed from the beginning. In this case, since it is impossible to make the piece reach the bottom-rightmost cell, output -1.

This sample input satisfies the constraints of Subtasks $2, 3, 4$.

Sample Input 3

1 5
.#.#.

Sample Output 3

4

This sample input satisfies the constraints of all subtasks.

Sample Input 4

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

Sample Output 4

12

This sample input satisfies the constraints of Subtasks $2, 3, 4$.

Sample Input 5

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

Sample Output 5

12

This sample input satisfies the constraints of Subtasks $3, 4$.