격자의 분리자

연결된 무향 그래프 G=(V, E)가 주어진다. V는 정점 집합이고 E는 간선 집합이다. 정점 집합 V의 부분집합 S를 제거했을 때 남은 그래프가 두 개의 연결 요소 W와 B로 나뉘면, S를 분리자라고 한다. 정점을 제거하면 그 정점에 연결된 모든 간선도 함께 제거된다. 이 상황을 [S, W, B]로 나타낸다.

이 문제에서는 격자 그래프의 분리자를 다룬다. 각 격자점은 정점이고, 한 정점은 상하좌우와 네 대각선 방향으로 인접한 최대 8개의 정점과 연결된다. 흰 영역은 W, 회색 영역은 S, 검은 영역은 B를 뜻한다고 생각할 수 있다.

처음 주어지는 분리자 S는 다음 조건을 만족한다.

1. S의 진부분집합은 분리자가 아니다.
2. S는 네 모서리를 제외한 맨 윗줄의 정점 하나와 맨 아랫줄의 정점 하나를 포함한다.
3. S를 위에서 아래로 따라갈 때, 아래로 내려간 뒤 다시 위로 올라가는 움직임은 없다.

다음 두 단계로 S를 바꿀 수 있다.

1. B에 속한 정점 몇 개를 골라 S에 추가한다. 고른 각 정점의 바로 왼쪽 정점은 S에 속해야 한다.
2. 처음부터 S에 속했던 정점 몇 개를 제거하여 W에 넣는다. 단, 1단계에서 새로 추가한 정점은 제거할 수 없다.

이 과정을 거친 뒤에도 S가 분리자이도록 하면서, S의 크기를 최소화하라.

입력은 여러 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 격자의 크기를 나타내는 두 정수 N, M이 주어진다. 격자의 크기는 N x M이며, 3 <= N, M <= 200이다.

다음 N개의 줄에는 길이 M의 문자열이 하나씩 주어진다. 각 문자는 S, W, B 중 하나이며, 해당 정점이 어느 집합에 속하는지를 나타낸다. 모든 W는 S의 왼쪽에 있다. 잘못된 입력은 주어지지 않는다.

입력의 끝에는 0 0이 주어진다.

각 테스트 케이스마다 한 줄에 가능한 S의 최소 크기를 출력한다.