Допоможіть Музею
Національна асоціація кураторів музеїв звернулася до вас із цікавою проблемою. Президент країни, щоб покращити свій публічний імідж, вирішив відвідати різні художні музеї в країні, щоб створити враження, що він є витонченою людиною. Однак, будучи дуже зайнятою особою і нічого не знаючи про мистецтво, він наклав два обмеження на відвідування:
У кожному музеї він хоче побачити роботи одного і тільки одного художника, щоб він міг легко підготуватися до візиту і виглядати як знавець мистецтва. Однак він не обов'язково повинен бачити всі роботи цього художника.
Він не хоче витрачати час і вимагає пройти експозицію, слідуючи найкоротшим можливим шляхом.
Куратори готові виконати вимоги Президента, але вони не хочуть перерозподіляти шедеври в експозиції тільки для того, щоб отримати прямий шлях. Їх єдина поступка - тимчасово обміняти місцями два шедеври, якщо це допоможе отримати коротший шлях.
Ви повинні написати програму, яка отримує на вхід розташування експозиції і знаходить найкоротший шлях відповідно до вищезазначених обмежень. Щоб полегшити ваше завдання, куратори вже визначили стандартне розташування. Рисунок 1 показує одне з таких розташувань.
Рисунок 1: Розташування музею
Прогулянка Президента завжди починається від лівої стіни (X = 1, будь-яка Y) і закінчується на правій стіні (X = X_max, будь-яка Y). Прогулянка може здійснюватися горизонтально або вертикально; діагональні рухи не дозволені. Роботи даного художника всі позначені однією і тією ж великою літерою (A, B, C тощо). З Рисунка 1 можна проілюструвати кілька випадків:
Якщо президент хоче побачити роботи художника A, немає шляху зліва направо. Такий шлях можна отримати, якщо роботу художника B в (6, 6) обміняти з роботою художника A з (1, 8), (7, 8), (8, 8), (10, 6), (11, 6) або (11, 3).
Якщо президент хоче побачити роботи художника B, вже є шлях, що починається в (1, 10) і закінчується в (11, 5). Коротший шлях можна отримати, якщо роботу D в (11, 7) обміняти з роботою художника B, наприклад, з (10, 6).
Якщо президент хоче побачити роботи художника C, вже є прямий шлях з (1, 1) до (1, 11), і коротший шлях не може бути отриманий.
Якщо президент хоче побачити роботи D, E або F, немає можливості отримати шлях зліва направо.
Вхідні дані
Вхідний файл може містити кілька екземплярів задачі. Кожен екземпляр має наступний формат (всі числа є додатними цілими):
Перша строка містить цілі числа X_max і Y_max, розміри розташування. Ви можете припустити, що 1 ≤ X_max,Y_max ≤ 100.
Друга строка містить літеру художника (велика літера), роботи якого будуть відвідані.
Y_max рядків, кожен з X_max літерами (без пробілів між ними). Перша вхідна строка відповідає індексу Y_max, друга строка індексу Y_max-1, і так далі, до останньої строки, яка відповідає індексу 1.
Строка, що містить два нулі, завершує вхідний файл. Числа розділені пробілами.
Вихідні дані
Для кожного екземпляра задачі ваша програма повинна виробляти вихід наступним чином.
Якщо шлях існує, ваша програма повинна спочатку вивести один рядок з повідомленням "Exchange (x,y) and (u,v)", якщо обмін відбудеться, або "No exchange" в іншому випадку. Після цього повинен бути виведений найкоротший шлях, одна координата на рядок. У випадку, якщо більше одного шляху є найкоротшим, може бути виведений будь-який з них, за винятком того, що шлях без обміну повинен бути відданий перевага перед тими, що з обмінами.
Якщо шлях не існує, ваша програма повинна вивести лише один рядок з повідомленням "No path".
Вихід кожного екземпляра завершується порожнім рядком.