Shortest Path in a Grid with Obstacles

You are given an m x n grid. Each cell in the grid is either empty (.) or an obstacle (#). Your task is to find the shortest path from the top‐left corner (cell (1, 1)) to the bottom‐right corner (cell (m, n)) while only moving up, down, left, or right.

If a path exists, print the length of the path (i.e. the number of moves from start to finish), then print the total number of cells in the path (including both endpoints) followed by the coordinates of each cell in the order from the start to the destination. If no such path exists, output -1.

Constraints:
\(1 \le m, n \le 100\) and the grid may contain any number of obstacles.

Note: The path length is defined as the number of moves (edges) traversed, while the number of cells includes the starting and ending cells.

inputFormat

The input is read from standard input (stdin). The first line contains two integers m and n separated by a space, representing the number of rows and columns of the grid, respectively. The next m lines each contain a string of length n consisting of characters . (empty cell) or # (obstacle).

outputFormat

If a valid path exists, the output (printed to stdout) should consist of:

1. The length of the shortest path (i.e. number of moves) on the first line.
2. The total number of cells in the path on the second line.
3. Each subsequent line contains two integers representing the row and column of a cell in the path, listed in order from the start to the destination.

If no path exists, simply output -1.

## sample

3 3
.#.
.#.
...

4
5
1 1
2 1
3 1
3 2
3 3

</p>