Problem Description

There is a grid of squares that spans vertically $H$ squares and horizontally $W$ squares, with each square painted either white or black. The square at the $i$-th row from the top and the $j$-th column from the left is denoted as $(i, j)$. Snuke wants to play a game using this grid. At the start of the game, the character "Kenus" is located at square $(1, 1)$. The player repeatedly moves Kenus one square at a time in one of the four directions: up, down, left, or right. The game is cleared if Kenus can reach square $(H, W)$ passing only through white squares.

Before starting the game, Snuke can change the color of some white squares to black. However, the colors of squares $(1, 1)$ and $(H, W)$ cannot be changed, and all color changes must be made before the game starts. The score of Snuke is the number of times he changes the color of the squares before the game starts. Determine the maximum possible score Snuke can achieve. If it is impossible for Kenus to reach square $(H, W)$ regardless of how Snuke changes the colors of the squares, output $-1$.

The color information for each square is given as a character $s_{i, j}$. If the square $(i, j)$ is initially painted white, $s_{i, j}$ is .; if the square $(i, j)$ is initially painted black, $s_{i, j}$ is #.

Input Format

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

$ H $ $ W $ $ s_{1, 1}s_{1, 2}s_{1, 3}...s_{1, W} $ $ s_{2, 1}s_{2, 2}s_{2, 3}...s_{2, W} $ $ : $ $ : $ $ s_{H, 1}s_{H, 2}s_{H, 3}...s_{H, W} $

Output Format

Output the maximum possible score Snuke can achieve. If it is impossible for Kenus to reach square $(H, W)$ regardless of how Snuke changes the colors of the squares, output $-1$.

Sample Input and Output

Sample Input #1

3 3
..#
#..
...

Sample Output #1

2

Sample Input #2

10 37
.....................................
...#...####...####..###...###...###..
..#.#..#...#.##....#...#.#...#.#...#.
..#.#..#...#.#.....#...#.#...#.#...#.
.#...#.#..##.#.....#...#.#.###.#.###.
.#####.####..#.....#...#..##....##...
.#...#.#...#.#.....#...#.#...#.#...#.
.#...#.#...#.##....#...#.#...#.#...#.
.#...#.####...####..###...###...###..
.....................................

Sample Output #2

209

Notes/Hints

Constraints

• $H$ is an integer between $2$ and $50$ inclusive.
• $W$ is an integer between $2$ and $50$ inclusive.
• $s_{i, j}$ is either . or # for $1 \leq i \leq H$, $1 \leq j \leq W$.
• $s_{1, 1}$ and $s_{H, W}$ are .

Sample Explanation 1

By changing the colors of the squares as shown in the figure below, a score of $2$ can be achieved.

见题面 Input 部分

见题面 Output 部分