Stable Table

문제

Avant-garde carpenter Mort S. Tenon specializes in assembling furniture out of odd-shaped pieces of wood. Using strong glue and cleverly-hidden weights and floor anchors, Tenon can make tables that appear to defy gravity, as shown in Figure 1(b). He begins by creating a rectangular block composed of pieces of wood whose vertical cross-sections are rectilinear polygons, that is, polygons whose sides are either horizontal or vertical. Some of these pieces may have holes containing other pieces. Then he removes as many pieces as possible, leaving a structure consisting of the smallest possible number of stable pieces that include the entire top surface of the rectangular block. For aesthetic reasons (something having to do with patterns of wood grain), Mort never has more than two pieces forming the table's top surface.

Figure 1(a) shows an initial rectangular block with cuts. By removing the pieces numbered $11$ and $22$, $44$ through $77$, and $1111$ and $1212$, he produces the stable table shown in Figure 1(b). A piece is considered stable if either it is directly in contact with the floor or at least one of its horizontal edges lies above and is in contact with a horizontal edge of a stable piece. The region of contact between two adjacent pieces must have positive area in order for the contact to be stable; contact only along a corner is not sufficient.

(a) Original rectangular block	(b) A five-piece stable table

Figure K.1: Illustration of Sample Input 1

Given a description of the initial rectangular block of pieces, help Mort determine a stable table with the minimum number of pieces.

입력

The first line of input contains two positive integers $hh$ and $ww$ ($1\le h,w\le 1001\; \backslash le\; h,w\; \backslash le\; 100$), the height and width of the initial block of pieces. Each of the remaining $hh$ lines contains $ww$ positive integers describing which piece is associated with each $1\times 11\backslash times\; 1$ unit of the block. Pieces all have distinct numbers from $11$ up through the number of pieces in the block. There can be at most $99029\backslash ,902$ pieces since the first row of input can have at most two piece numbers. Pieces may have holes containing other pieces; each piece is connected using shared edges among the $1\times 11\backslash times\; 1$ units comprising the piece.

출력

Output a single integer equal to the minimum number of pieces in a stable table.

8 12
13 13 13 13 13 13 13 13 3 3 3 3
13 13 13 13 13 13 13 13 3 2 2 3
13 13 13 1 1 13 13 13 3 3 3 3
13 13 13 1 1 13 13 13 8 11 11 11
13 13 13 13 13 7 8 8 8 11 11 11
13 13 13 13 13 7 9 9 9 11 11 11
4 4 4 4 6 6 10 10 10 11 12 12
5 5 5 5 6 6 10 12 12 12 12 12

5

3 4
8 8 8 8
5 6 7 8
1 2 3 4

2