유역

지질학자들은 때때로 빗물이 흘러 내려가는 곳을 기준으로 육지의 한 영역을 서로 다른 구역으로 나눈다. 이러한 구역을 배수 유역이라고 한다.

고도 지도(고도로 이루어진 2차원 배열)가 주어질 때, 다음 규칙에 따라 같은 배수 유역에 속한 위치들이 같은 레이블을 갖도록 지도에 레이블을 지정하라.

• 각 셀에서 물은 그 셀의 4개 이웃 셀 중 최대 하나로 흘러 내려간다.

• 각 셀에 대해, 그 셀의 4개 이웃 셀 중 현재 셀보다 고도가 낮은 셀이 하나도 없다면 물은 흐르지 않으며, 현재 셀을 싱크라고 한다.

• 그렇지 않으면 물은 현재 셀에서 고도가 가장 낮은 이웃으로 흐른다.

• 동률인 경우, 물은 다음 목록에서 고도가 가장 낮은 방향 중 가장 먼저 나오는 방향을 선택한다: 북, 서, 동, 남.

직접 또는 간접적으로 같은 싱크로 배수되는 모든 셀은 같은 배수 유역에 속한다. 각 유역에는 고유한 소문자 레이블을 지정하되, 지도의 행을 위에서 아래로 이어 붙였을 때 만들어지는 문자열이 사전순으로 가장 작아야 한다. (특히 가장 북서쪽 셀이 속한 유역에는 항상 'a' 레이블이 지정된다.)

제한

메모리 제한: 1 GB. T ≤ 100;

작은 데이터 세트

시간 제한: 25초. 1 ≤ H, W ≤ 10; 0 ≤ 고도 < 10. 유역은 최대 두 개이다.

큰 데이터 세트

시간 제한: 30초. 1 ≤ H, W ≤ 100; 0 ≤ 고도 < 10,000. 유역은 최대 26개이다.

입력 파일의 첫 번째 줄에는 지도의 수 T가 주어진다. 이어서 T개의 지도가 주어지며, 각 지도는 한 줄에 두 정수 H와 W로 시작한다. 이는 셀 단위로 나타낸 지도의 높이와 너비이다. 다음 H개의 줄에는 각각 지도의 한 행이 북쪽에서 남쪽 순서로 주어지며, 각 줄에는 셀의 고도를 나타내는 W개의 정수가 서쪽에서 동쪽 순서로 주어진다.

각 테스트 케이스마다 1+H개의 줄을 출력한다. 첫 번째 줄은 다음 형식이어야 한다.

Case #X:

여기서 X는 1부터 시작하는 테스트 케이스 번호이다. 다음 H개의 줄에는 각 셀의 유역 레이블을 입력에 나타난 것과 같은 순서로 나열해야 한다.

케이스 #1에서는 오른쪽 위 모서리와 왼쪽 아래 모서리가 싱크이다. 대각선 위의 물은 더 낮은 고도 때문에 왼쪽 아래를 향해 흐른다 (5 대 6).