카이로 통로

카이로 오각형 타일링은 준정오각형으로 평면을 빈틈없이 덮는 방법이다. 카이로의 도로 몇 곳이 이 무늬를 변형해 포장되어 있어서 붙은 이름이다.

오각형마다 비어 있거나(흰색) 칠해져 있는(회색) 유한한 타일링을 생각하자. 통로는 서로 이어진 빈 오각형의 극대 집합 가운데 타일링의 네 경계에 모두 닿는 것이다. 두 오각형은 변을 공유할 때 인접하고, 꼭짓점 하나만 맞닿으면 인접하지 않는다. 한 타일링에 통로는 많아야 하나 있다. 통로에 군더더기 오각형이 없으면, 즉 통로에 속한 오각형 중 어느 하나를 칠해도 남은 오각형이 더는 통로가 되지 않으면 그 통로를 최소 통로라고 한다.

그림은 타일링 네 개를 보여준다. 앞의 세 타일링에는 통로가 있고 노란색으로 칠했다. (a)와 (b)의 통로는 최소이지만 (c)의 통로는 최소가 아니다. 예를 들어 X 표시를 한 타일을 칠해도 통로는 그대로 남는다. 맨 오른쪽 타일링에는 통로가 없다. (a)와 (c)는 첫 번째 예제에 주어진 두 타일링이다.

타일링마다 통로가 있는지, 있다면 최소 통로인지 판정하라. 최소 통로이면 그 크기, 즉 통로에 속한 빈 오각형의 개수를 구하라.

첫 줄에 타일링의 개수 $T$가 주어진다. 타일링마다 첫 줄에 정수 $N$과 $M$이 공백을 사이에 두고 주어지고, 이어지는 $N$개 줄에 각각 이진수 숫자 $2M$개가 주어진다. 이 숫자는 오각형 쌍 $a_{ij}$, $b_{ij}$를 나타내며 0은 빈 오각형, 1은 칠해진 오각형이다. $i$번째 줄은 $a_{i1}$, $b_{i1}$, $a_{i2}$, $b_{i2}$ 순으로 $b_{iM}$까지 나열한다.

타일링은 정사각형 $N \times M$개로 이루어진 격자로 읽는다. $i$행 $j$열 정사각형이 오각형 쌍 하나를 담는다. $i + j$가 짝수이면 $a_{ij}$가 그 정사각형의 왼쪽 절반, $b_{ij}$가 오른쪽 절반이다. $i + j$가 홀수이면 $a_{ij}$가 위쪽 절반, $b_{ij}$가 아래쪽 절반이다. 그래서 가로로 놓인 쌍과 세로로 놓인 쌍이 체스판처럼 번갈아 나타난다. 두 오각형은 이렇게 나눈 절반끼리 길이가 0보다 큰 선분을 공유할 때 인접하고, 절반이 바깥 직사각형의 한 변에 닿으면 그 오각형은 그 경계에 닿은 것이다.

$T$개의 줄을 출력한다. $k$번째 줄에는 $k$번째 타일링에 최소 통로가 있으면 그 통로의 크기를, 없으면 NO MINIMAL CORRIDOR를 출력한다. NO MINIMAL CORRIDOR는 적힌 그대로 출력한다.

• $1 \le T \le 10$, 타일링의 개수
• 모든 타일링 $k$에 대해 $1 \le N_k$, $1 \le M_k$
• $\sum_{k=1}^{T} N_k \le 250$, 격자 줄 수의 합
• $\sum_{k=1}^{T} M_k \le 250$, 한 줄에 놓인 오각형 쌍 개수의 합