지붕 칠하기

베를란트의 왕은 모든 것에 질서가 잡혀 있기를 바란다. 예를 들어 지도에 나타난 베를란트의 수도는 도시의 구획에 해당하는 칸들로 이루어진 직사각형 격자이다.

왕은 최근 모든 구획의 지붕을 빨간색이나 파란색 중 한 가지 색으로 통일해서 칠하라는 칙령을 내렸다. 베를란트의 수도에는 도시 전체가 칙령을 지켰는지 확인하는 위원회가 올 예정이며, 위원회는 한 구획에서 변을 맞댄 인접 구획으로 이동한다. 검사를 성공적으로 마치려면 위원회가 어느 구획에서든 다른 모든 구획으로 이동할 수 있어야 한다.

재무장관은 위원회가 특이한 요구를 한다는 사실을 알게 되었다. 위원회는 현재 있는 구획의 지붕과 인접 구획의 지붕 색이 같으면 그 인접 구획으로 이동할 수 없다. 따라서 검사를 통과하려면 일부 구획은 지붕 전체를 다시 칠해야 한다. 재무장관은 비용을 아끼려고 한다. 그는 지붕 전체를 다시 칠해야 하는 구획 수의 최솟값을 구해 달라고 요청한다.

입력 파일의 첫째 줄에는 도시 지도의 행 수와 열 수를 나타내는 두 정수 $m$과 $n$이 주어진다 ($1\le m, n\le 1000$). 다음 $m$개의 줄에는 각각 $n$개의 기호가 주어지며, 각 기호는 '1' 또는 '2'이다. 기호 '1'은 해당 구획의 지붕이 모두 파란색임을, 기호 '2'는 지붕이 빨간색임을 나타낸다.

출력 파일에 지붕을 다시 칠해야 하는 구획 수의 최솟값을 나타내는 정수 하나를 출력한다.