ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

DSAP Vietnam Contest

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Rope in the Labyrinth

Time limit: 0.5 second
Memory limit: 64 MB
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 cells there is only one way to move from one cell to the other. There is a hook at each cell's center. In the labyrinth there are two special free cells, such that if you can connect the hooks of those two cells 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.

Input

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

Output

Print out in the single line the length (measured in the number of cells) of the required rope.

Sample

inputoutput
7 6
#######
#.#.###
#.#.###
#.#.#.#
#.....#
#######
8
To submit the solution for this problem go to the Problem set: 1145. Rope in the Labyrinth