세비야의 정원사 (Small)

문제

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

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

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

누가 누구를 사랑하는지 주어질 때, 모든 연인 쌍이 이어지도록 산울타리 미로를 만들거나 그런 미로가 없다고(IMPOSSIBLE) 판정하라.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $R$ 과 $C$ 가 있고, 다음 줄에는 1부터 $2(R+C)$ 까지의 정수를 한 번씩 모두 담은 순열이 있다. 각 정수는 신하의 번호다. 순열의 첫 번째와 두 번째 신하가 연인이므로 이어져야 하고, 세 번째와 네 번째 신하도 연인이므로 이어져야 한다. 나머지도 같은 방식이다.

제한

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

출력

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

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

힌트

세 번째 케이스에서 연인 쌍은 (8, 1), (4, 5), (2, 3), (7, 6)이다. 예제 출력을 그림으로 나타내면 다음과 같다.

세 번째 케이스에서는 다음 미로도 조건을 만족한다.

/\
\/

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

네 번째 케이스의 안뜰은 칸 하나뿐이므로, 그 둘레에 사는 신하는 위에서부터 시계 방향으로 1, 2, 3, 4번이다. 칸에 놓을 수 있는 것은 /와 \ 두 가지뿐이다. /를 놓으면 1번과 4번, 2번과 3번이 이어진다. \를 놓으면 1번과 2번, 3번과 4번이 이어진다. 그런데 이 케이스에서는 1번이 3번을, 2번이 4번을 사랑하므로 어느 쪽도 상사병에 걸린 신하에게 도움이 되지 않는다. 따라서 이 케이스는 IMPOSSIBLE이고, 오페라는 슬픈 아리아로 가득할 것이다.