A labyrinth with rectangular form and size m × n is divided into square cells with sides' length 1 by lines that are parallel with the labyrinth's sides. Each cell of the grid is either occupied or free. It is possible to move from one free cell to another free cells that share a common side with the cell. One cannot move beyond the labyrinth's borders. The labyrinth is designed pretty specially: for any two free cells there is only one way to move from one cell to the other.

Somewhere in the labyrinth there are two special free cells, with a hooks at their centers. If you can connect these hooks with a rope, the labyrinth's secret door will be automatically opened. The problem is to prepare a shortest rope that can guarantee, you always can connect the hooks of those two cells with the prepared rope regardless their position in the labyrinth.

The first line contains integers n and m (3 ≤ n, m ≤ 820). The next m lines describe the labyrinth. Each of them contains n characters. Each character is either "#" or ".", with "#" indicating an occupied cell, and "." indicating a free cell. There are at least two free cells in the labyrinth.

Output the length (measured in the number of cells) of the required rope.