시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 256 MB111100.000%

문제

The King of Berland loves order in everything. For instance, the capital of Berland as seen on the map is a rectangular field of cells, that correspond to city quarters.     

He recently has issued a decree stating that all roofs in a quarter must be painted the same color --- either red or blue. The capital of Berland is expecting a commission which will check the whole city for compliance, moving from one quarter to an adjacent by a side quarter. For a successful check, the commission must be able to reach any quarter from any other.

The Minister of Finance found out that the commission has a curious demand. They cannot move to an adjacent quarter if its roofs have the same color as roofs of the quarter they are currently in. Consequently, some quarters will have to repaint all their roofs to pass the check. The Minister of Finance wants to save money. He's asking you to find the minimal number of quarters where all roofs must be repainted.

입력

The first line of the input file contains two integers $m$ and $n$ --- the number of lines and columns in the city map ($1\le m, n\le 1000$). Next come $m$ lines consisting of $n$ symbols, with each symbol being either '1', or '2'. The symbol '1' means that all roofs in the corresponding quarters are blue, and the symbol '2' means that the roofs are red.

출력

In the output file, print a single integer --- the minimal number of quarters where roofs must be repainted.

예제 입력 1

1 4
2211

예제 출력 1

2