세비야의 정원사 (Large)

문제

당신은 어느 오페라의 단역인 세비야의 정원사다. 무대는 단위 칸으로 이루어진 $R$ 행 $C$ 열 직사각형 안뜰이다. 당신은 안뜰에 산울타리 미로를 설치해야 한다. 모든 칸에는 한 모서리에서 반대쪽 모서리로 대각선으로 뻗은 산울타리가 하나씩 있어야 한다. 한 칸에 놓을 수 있는 산울타리는 두 종류로, 왼쪽 아래에서 오른쪽 위로 가는 것을 /, 왼쪽 위에서 오른쪽 아래로 가는 것을 \로 나타낸다. 두 산울타리가 맞닿는 곳에서는 끊김 없는 벽이 생긴다.

안뜰 둘레에는 폭이 한 칸인 바깥 고리가 있고, 고리의 네 귀퉁이 칸은 없다. 바깥 고리의 각 칸에는 신하가 한 명씩 산다. 신하 번호는 맨 윗줄의 가장 왼쪽 칸을 1번으로 하여 시계 방향으로 매기며, 왼쪽 열의 가장 위 칸이 $2(R+C)$ 번이다. 예를 들어 $R = 2$ , $C = 2$ 일 때 바깥 고리의 번호는 다음과 같다. (아직 산울타리는 설치하지 않았다.)

이 특이한 오페라에서 사랑은 서로에게만 향한다. 모든 신하는 정확히 한 명의 다른 신하를 사랑하고, 그 신하도 오직 그 사람만 사랑한다. 신하는 모두 다른 신하와 마주치지 않고 산울타리 미로를 몰래 지나 연인에게 가고 싶어 한다. 즉 서로 사랑하는 두 신하는 미로 안의 경로로 연결되어야 하고, 이 경로는 다른 모든 경로와 산울타리 벽으로 분리되어야 한다. 모든 연인 쌍이 연결되기만 하면 미로에 어느 신하의 경로에도 속하지 않는 부분이 있어도 된다.

누가 누구를 사랑하는지가 주어질 때, 모든 연인 쌍이 연결되도록 산울타리 미로를 만들거나 그런 미로가 없으면 IMPOSSIBLE임을 판단하라.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어지고, 이어서 $T$ 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $R$ 과 $C$ 가 주어지고, 다음 줄에는 1 이상 $2(R+C)$ 이하의 모든 정수로 이루어진 순열이 주어진다. 각 정수는 신하의 번호다. 목록의 첫 번째와 두 번째 신하는 서로 사랑하므로 연결되어야 하고, 세 번째와 네 번째 신하도 서로 사랑하므로 연결되어야 한다. 이후도 마찬가지다.

제한

$1 \le T \le 500$
$1 \le R \times C \le 100$

출력

각 테스트 케이스마다 Case #x:만 담긴 줄을 하나 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호다. 조건을 만족할 수 없으면 IMPOSSIBLE이라는 줄을 하나 더 출력한다. 그렇지 않으면 조건을 만족하는 산울타리 미로를 나타내는 $R$ 개의 줄을 더 출력한다. 각 줄은 $C$ 개의 문자로 이루어지고, 모든 문자는 / 또는 \다. 미로에 빈 칸을 남기면 안 된다.

조건을 만족하는 미로가 여럿이면, $R$ 개의 줄을 위에서부터 차례로 이어 붙인 문자열이 사전순으로 가장 앞서는 미로를 출력한다. 이때 /가 \보다 앞선다.

힌트

3번 케이스에서 서로 사랑하는 신하 쌍은 (8, 1), (4, 5), (2, 3), (7, 6)이다. 다음은 예제 출력을 그림으로 나타낸 것이다.

3번 케이스는 다음 미로도 조건을 만족한다.

/\
\/

하지만 줄을 이어 붙인 문자열 /\\/는 //\/보다 사전순으로 뒤이므로 정답은 예제 출력의 미로다.

4번 케이스는 안뜰이 한 칸뿐이므로 그 둘레에 사는 신하는 위에서부터 시계 방향으로 1, 2, 3, 4번이다. 그 한 칸에 놓을 수 있는 것은 /와 \ 두 가지뿐이다. /를 놓으면 1번과 4번, 2번과 3번이 연결된다. \를 놓으면 1번과 2번, 3번과 4번이 연결된다. 하지만 이 케이스에서는 1번이 3번을, 2번이 4번을 사랑하므로 어느 쪽도 사랑에 빠진 신하들에게 도움이 되지 않는다. 따라서 이 케이스는 IMPOSSIBLE이고, 오페라는 슬픈 아리아로 가득할 것이다!