Shortest Path in a Grid

You are given a grid with N rows and M columns. Each cell in the grid is either free ('.') or blocked ('#'). Your task is to compute the length of the shortest path from the top-left cell (at position (0,0)) to the bottom-right cell (at position (N-1, M-1)) moving only up, down, left, or right. If either the starting cell or the destination cell is blocked, or if there is no valid path, output -1.

The problem can be formally described using the following formula:

$$\text{distance} = \min_{\text{path } P}\left(\sum_{(i,j)\in P} 1\right)$$

If no such path exists, then \(\text{distance} = -1\).

Input is read from standard input and output is printed to standard output.

inputFormat

The first line contains two integers N and M separated by a space, which represent the number of rows and columns of the grid, respectively. The next N lines each contain a string of length M consisting only of the characters '.' and '#' representing the grid cells.

outputFormat

Output a single integer representing the length of the shortest path. If there is no valid path, output -1.

## sample

4 4
...#
##.#
....
.##.

6