걸리버

릴리퍼트 사람들이 사는 섬에서 위대한 여행가 걸리버가 환호 소리에 잠에서 깼다. 처음의 소동이 지나간 뒤, 릴리퍼트 사람들은 이웃 섬 블레푸스쿠와 벌이는 전쟁 이야기를 들려주었다.

사실 블레푸스쿠와 릴리퍼트는 오래전 같은 섬에 살았다. 어느 날 누군가가 달걀을 삶은 뒤, 두 나라는 달걀의 어느 쪽부터 먹어야 하는지를 두고 합의하지 못했다. 다툼은 전쟁으로 커졌고, 결국 그들은 섬을 둘로 나누기로 했다. 남쪽은 블레푸스쿠가, 북쪽은 릴리퍼트가 차지했다.

놀랍게도 이 섬은 직사각형 모양이며, R × C개의 정사각형 구획으로 이루어져 있다. 몇몇 구획은 이미 물에 잠겨 있고, 사람들은 섬을 나누기 위해 추가로 몇 개의 구획을 물에 잠기게 하려고 한다. 섬은 적어도 두 부분으로 나뉘어야 하며, 한 부분에는 맨 위 행 전체(북쪽)가, 다른 부분에는 맨 아래 행 전체(남쪽)가 포함되어야 한다. 물에 잠기지 않은 두 구획 사이를 상하좌우로 이동해서 서로 도달할 수 있으면 두 구획은 같은 부분에 속한다.

아래 그림은 사건 전의 섬과, 섬을 나누기 위해 추가로 물에 잠기게 한 구획의 한 가지 모습을 보여 준다. 검은 구획은 이미 물에 잠겨 있던 구획이다.

오랫동안 전해 내려온 질문은 다음과 같다. 섬의 북쪽과 남쪽이 완전히 분리되도록 만들기 위해, 추가로 물에 잠기게 해야 하는 구획 수의 최솟값은 얼마인가? 그 값을 계산하는 프로그램을 작성하라.

첫째 줄에 섬의 행 수와 열 수를 나타내는 두 정수 R과 C가 주어진다. (3 ≤ R, C ≤ 1 000)

다음 R개 줄에는 길이 C의 문자열이 하나씩 주어진다. 각 문자는 . 또는 #이다. #는 이미 물에 잠긴 구획을 뜻한다.

입력으로 주어지는 섬에서 물에 잠기지 않은 모든 구획은 하나의 연결된 부분을 이루며, 맨 위 행과 맨 아래 행에는 물에 잠긴 구획이 없다.

섬의 북쪽과 남쪽을 분리하기 위해 추가로 물에 잠기게 해야 하는 구획 수의 최솟값을 출력한다.