Gulliver

On an island inhabited by the Lilliputians, the great traveler Gulliver woke to the sound of cheering. After the initial commotion, the Lilliputians told him about their war with the neighboring island of Blefuscu.

Long ago, Blefuscu and Lilliput lived on the same island. After someone boiled an egg, the two nations could not agree on which end of the egg should be eaten first. The dispute grew into a war, and in the end they decided to divide the island in two. Blefuscu took the south, and Lilliput took the north.

By a miracle, the island is a rectangle made of R × C square parcels. Some parcels are already underwater, and the people want to flood several additional parcels to divide the island. The island must be split into at least two parts: one containing the entire top row (the north side), and another containing the entire bottom row (the south side). Two parcels that are not underwater belong to the same part if one can move between them using only up, down, left, and right moves.

The figure below shows an island before the incident and one way to flood additional parcels so that it becomes separated. Black parcels were already underwater.

The question passed down for generations is this: what is the minimum number of additional parcels that must be flooded so that the north and south sides of the island become completely separated? Write a program that computes that number.

The first line contains two integers R and C, the number of rows and columns of the island. (3 ≤ R, C ≤ 1 000)

Each of the next R lines contains a string of length C. Each character is either . or #. A # represents a parcel that is already underwater.

In the given island, all parcels that are not underwater form one connected component, and there are no underwater parcels in the top or bottom row.

Output the minimum number of additional parcels that must be flooded to separate the north and south sides of the island.