현상 유지는 없다

Dr. Horrible은 악당 연맹(Evil League of Evil)에 꼭 가입하고 싶지만, 자신이 자칭하는 천재 악당임을 증명하는 데 애를 먹고 있다. 연맹을 철제 말굽으로 다스리는 Bad Horse는 그의 지원서를 극도로 의심스러운 눈으로 심사하는 중이다. 게다가 숙적인 Captain Hammer -- 대중의 영웅이자 기업의 앞잡이 -- 는 이 가엾은 악당의 삶을 끊임없이 꼬이게 만든다. 하지만 이제 모든 것이 달라지려 한다. Dr. Horrible은 큰 강도 행각을 벌일 준비를 마쳤다. 그의 냉동 광선을 완성하는 데 필요한 wonderflonium이 택배 밴으로 운송되고 있으니, 식은 죽 먹기다. 안타깝게도 그렇게 쉽지만은 않다. 밴을 조종하려고 만든 장치의 배선이 뒤엉켜 버려서 풀어내야 한다. 룸메이트 Moist에게 시킬 수도 있지만, (뻔한 이유로) Moist를 회로 근처에 두는 것은 좋은 생각이 아니다. 그러니 당신이 직접, 그것도 빨리 해내야 한다.

그림 5: 연결점 레이블

당신의 임무는 여러 회로판에 대해, 어떤 전선의 시작 위치가 주어졌을 때 그 전선이 끝나는 위치를 알아내는 것이다. 회로판은 정사각형 칸들로 이루어진 직사각형 격자다. 각 칸에는 8개의 연결점이 있으며, 한 변마다 2개씩 배치된다. 한 칸은 0개에서 4개(양 끝 포함)까지의 전선을 가질 수 있고, 각 전선은 그 칸의 한 연결점과 다른 연결점을 잇는다. 모든 연결점은 최대 하나의 전선에만 사용되며, 분기는 없다.

칸의 연결점은 위쪽 변의 왼쪽 연결점에서 시작하여 시계 방향으로 돌면서 A부터 H까지(항상 대문자로) 이름 붙인다. 즉 A와 B는 위쪽 변의 왼쪽·오른쪽 연결점, C와 D는 오른쪽 변의 위·아래 연결점, E와 F는 아래쪽 변의 오른쪽·왼쪽 연결점, G와 H는 왼쪽 변의 아래·위 연결점이다. 한 칸은 그 칸이 담고 있는 전선들로 기술한다. 예를 들어 위쪽 변 왼쪽 연결점에서 오른쪽 변 아래 연결점으로 가는 전선, 아래쪽 변 왼쪽 연결점에서 아래쪽 변 오른쪽 연결점으로 가는 전선, 위쪽 변 오른쪽 연결점에서 왼쪽 변 위 연결점으로 가는 전선이 있는 칸은 "AD BH EF"로 기술된다. 각 쌍은 알파벳 순으로 적고(HB가 아니라 BH), 한 칸 안의 쌍들도 알파벳 순으로 나열한다.

칸들은 모든 변에서 서로 맞닿아 회로판을 이룬다. 임의의 칸에 대해, 연결점 A와 B는 위쪽에 있는 칸의 F와 E에 각각 이어지며, 아래쪽 칸에 대해서는 그 반대다. 연결점 C와 D는 오른쪽에 있는 칸의 H와 G에 각각 이어지며, 왼쪽 칸에 대해서는 그 반대다. 어떤 칸이 공유하는 변 위의 연결점에 닿는 전선을 가지고 있다면, 인접한 칸의 대응 연결점이 그 경로를 반드시 이어 준다. 끊긴 경로는 없으며, 모든 경로는 회로판의 바깥 가장자리에서 시작하고 끝난다.

입력은 여러 개의 퍼즐 세트로 이루어진다. 각 퍼즐 세트는 두 부분, 즉 회로판 기술과 시작점 목록으로 나뉜다.

회로판 기술은 공백으로 구분된 두 정수 $h$와 $w$($1 \le h, w \le 20$)가 담긴 한 줄로 시작한다. 이는 각각 칸 단위로 잰 회로판의 높이와 너비다. 그다음에는 $n$개($1 \le n \le h \cdot w$)의 칸 기술 줄이 순서와 무관하게 이어진다. 각 줄은 한 칸을 기술하며 그 칸의 번호로 시작한다. 칸은 왼쪽에서 오른쪽, 위에서 아래로 $1$부터 차례로 번호를 매기며, 예를 들어 오른쪽 위 칸의 번호는 $w$다. 번호 다음에는 위에서 설명한 형식대로 그 칸의 배선이 오고, 번호와 모든 전선 쌍은 공백 하나로 구분된다. 모든 칸이 기술되는 것은 아니며, 한 칸은 한 회로판에서 많아야 한 번 기술된다. 기술되지 않은 칸에는 전선이 없다.

회로판 기술과 시작점 목록은 $0$ 하나만 있는 줄로 구분된다. 시작점은 그다음 줄에 주어지며, 각 시작점은 숫자 바로 뒤에 문자가 붙은 형태이고 서로 공백 하나로 구분된다. 숫자는 칸 번호, 문자는 시작할 연결점이다. 회로판 바깥쪽에 있는 연결점만, 그리고 실제로 전선이 사용하는 연결점만 주어진다. 이 줄 다음에는 다음 퍼즐 세트가 시작되기 전에 빈 줄이 하나 온다.

입력의 끝은 퍼즐 세트의 첫 줄 자리에 공백으로 구분된 두 개의 $0$("0 0")이 오는 것으로 표시된다.

각 퍼즐 세트마다 한 줄에 "Board", 공백, 회로판 번호(첫 퍼즐 세트가 $1$번이고 이후 세트마다 $1$씩 증가), 그리고 콜론(":")을 차례로 출력한다.

그다음, 그 세트의 각 시작점에 대해 "{시작점} is connected to {끝점}" 형식으로 한 줄씩 출력한다. 예를 들어 시작점이 1A이고 전선이 9H에서 끝난다면 그 줄은 "1A is connected to 9H"가 된다. 대소문자를 구분한다. 전선은 양방향이므로, 같은 퍼즐에서 시작점이 9H였다면 출력은 "9H is connected to 1A"가 된다. 시작점과 끝점의 문자 부분은 반드시 대문자여야 한다. 그 밖의 다른 기호나 문장 부호는 없어야 한다.

연속한 퍼즐 세트의 출력은 빈 줄로 구분한다.

그림 6: 첫 번째 예제