박물관을 도와주세요

전국 박물관 큐레이터 협회가 흥미로운 문제를 하나 들고 찾아왔다. 국가의 대통령은 자신의 대외 이미지를 개선하기 위해, 자신이 교양 있는 사람이라는 인상을 주고자 여러 미술관을 방문하기로 했다. 그러나 대통령은 매우 바쁜 사람이고 미술에 대해 아무것도 모르기 때문에, 방문에 두 가지 제약을 걸었다.

1. 각 미술관에서 오직 한 작가의 작품만 보고자 한다. 그래야 방문 전에 쉽게 준비해서 예술 감식가인 척할 수 있기 때문이다. 다만 그 작가의 모든 작품을 볼 필요는 없다.
2. 시간을 낭비하고 싶지 않으므로, 가능한 한 가장 짧은 경로를 따라 전시장을 걸어가야 한다.

큐레이터들은 대통령의 요구를 따르려 하지만, 곧은 경로를 얻기 위해 걸작들의 배치를 바꾸고 싶지는 않다. 그들이 양보할 수 있는 것은, 더 짧은 경로를 얻는 데 도움이 된다면 걸작 두 점의 위치를 임시로 맞바꾸는 것뿐이다.

전시장의 배치를 입력으로 받아 위 제약에 따라 가장 짧은 경로를 찾는 프로그램을 작성하라. 여러분의 작업을 돕기 위해 큐레이터들이 이미 표준 배치를 정해 두었다. 그림 7은 그러한 배치 하나를 보여준다.

그림 7: 박물관의 배치

대통령의 산책은 항상 왼쪽 벽(X = 1, Y는 임의)에서 시작하여 오른쪽 벽(X = Xmax, Y는 임의)에서 끝난다. 산책은 가로 또는 세로로만 할 수 있으며, 대각선 이동은 허용되지 않는다. 주어진 작가의 작품은 모두 같은 대문자(A, B, C 등)로 표시되어 있다. 그림 1에서 몇 가지 경우를 살펴볼 수 있다.

1. 대통령이 작가 A의 작품을 보고자 하면, 왼쪽에서 오른쪽으로 가는 경로가 없다. 이러한 경로는 (6, 6)에 있는 작가 B의 작품을 (1, 8), (7, 8), (8, 8), (10, 6), (11, 6), (11, 3) 중 하나에 있는 작가 A의 작품과 맞바꾸면 얻을 수 있다.
2. 대통령이 작가 B의 작품을 보고자 하면, (1, 10)에서 시작하여 (11, 5)에서 끝나는 경로가 이미 있다. (11, 7)에 있는 D의 작품을 작가 B의 작품, 예를 들어 (10, 6)에 있는 것과 맞바꾸면 더 짧은 경로를 얻을 수 있다.
3. 대통령이 작가 C의 작품을 보고자 하면, (1, 1)에서 (1, 11)로 가는 곧은 경로가 이미 있고, 더 짧은 경로는 얻을 수 없다.
4. 대통령이 D, E, F의 작품을 보고자 하면, 왼쪽에서 오른쪽으로 가는 경로를 얻을 방법이 없다.

입력 파일에는 여러 개의 문제 인스턴스가 들어 있을 수 있다. 각 인스턴스의 형식은 다음과 같다(모든 수는 양의 정수).

1. 첫 줄에는 배치의 크기인 정수 Xmax와 Ymax가 주어진다. 1 ≤ Xmax, Ymax ≤ 100이라고 가정해도 좋다.
2. 둘째 줄에는 작품을 관람할 작가의 대문자 알파벳이 주어진다.
3. Ymax개의 줄이 이어지며, 각 줄에는 Xmax개의 글자가 공백 없이 주어진다. 첫 번째 입력 줄은 인덱스 Ymax에, 두 번째 줄은 인덱스 Ymax − 1에 대응하며, 마지막 줄은 인덱스 1에 대응한다.

두 개의 0이 들어 있는 줄이 입력 파일의 끝을 나타낸다. 수는 공백으로 구분한다.

각 문제 인스턴스에 대해 프로그램은 다음과 같이 출력해야 한다.

경로가 존재하면, 먼저 교환이 일어날 경우 “Exchange (x,y) and (u,v)”라는 메시지를, 그렇지 않으면 “No exchange”를 한 줄에 출력한다. 그다음 가장 짧은 경로를 좌표 한 줄에 하나씩 출력한다. 가장 짧은 경로가 여러 개면 그중 아무거나 출력해도 되지만, 교환이 없는 경로를 교환이 있는 경로보다 우선해야 한다.

경로가 존재하지 않으면 “No path”라는 메시지를 한 줄만 출력한다.

각 인스턴스의 출력은 빈 줄로 끝난다.