Cairo Corridor

The Cairo pentagonal tiling covers the plane with semiregular pentagons. It is named after Cairo, where several streets are paved with variations of the pattern.

Consider a bounded tiling in which every pentagon is either clear (white) or filled in (grey). A corridor is a maximal set of clear pentagons, connected to one another, that reaches all four borders of the tiling. Two pentagons are adjacent when they share an edge; sharing a single corner is not enough. A tiling has at most one corridor. A corridor is minimal when it has no superfluous pentagon, that is, when filling in any one pentagon of the corridor leaves a set that is no longer a corridor.

The figure shows four tilings. The first three have a corridor, drawn in yellow. The corridors of (a) and (b) are minimal, the corridor of (c) is not: fill in the tiles marked X, among others, and a corridor still exists. The rightmost tiling has no corridor. Tilings (a) and (c) are the two tilings of the first example.

For each tiling, decide whether a corridor exists and is minimal. When it is minimal, report the size of the corridor, that is, the number of clear pentagons in it.

The first line contains the number of tilings $T$. Each tiling starts with a line holding two integers $N$ and $M$ separated by a space. The next $N$ lines each contain $2M$ binary digits that give the pairs of pentagons $a_{ij}$, $b_{ij}$, where 0 is a clear pentagon and 1 is a filled one. Line $i$ lists $a_{i1}$, $b_{i1}$, $a_{i2}$, $b_{i2}$, and so on up to $b_{iM}$.

Read the tiling as a grid of $N \times M$ squares. The square in row $i$ and column $j$ holds one pair of pentagons. If $i + j$ is even, $a_{ij}$ is the left half of that square and $b_{ij}$ is the right half. If $i + j$ is odd, $a_{ij}$ is the top half and $b_{ij}$ is the bottom half. Horizontal pairs and vertical pairs therefore alternate like the squares of a checkerboard. Two pentagons are adjacent when their halves share a segment of positive length, and a pentagon reaches a border of the tiling when its half touches that side of the outer rectangle.

Print $T$ lines. Line $k$ holds the size of the corridor of the $k$-th tiling when that tiling has a minimal corridor, and NO MINIMAL CORRIDOR otherwise. Print the text NO MINIMAL CORRIDOR exactly as written.

• $1 \le T \le 10$, the number of tilings
• $1 \le N_k$ and $1 \le M_k$ for every tiling $k$
• $\sum_{k=1}^{T} N_k \le 250$, the total number of grid lines
• $\sum_{k=1}^{T} M_k \le 250$, the total number of tile pairs per line