Допоможіть Музею

Національна асоціація кураторів музеїв звернулася до вас із цікавою проблемою. Президент країни, щоб покращити свій публічний імідж, вирішив відвідати різні художні музеї в країні, щоб створити враження, що він є витонченою людиною. Однак, будучи дуже зайнятою особою і нічого не знаючи про мистецтво, він наклав два обмеження на відвідування:

1. У кожному музеї він хоче побачити роботи одного і тільки одного художника, щоб він міг легко підготуватися до візиту і виглядати як знавець мистецтва. Однак він не обов'язково повинен бачити всі роботи цього художника.

2. Він не хоче витрачати час і вимагає пройти експозицію, слідуючи найкоротшим можливим шляхом.

Куратори готові виконати вимоги Президента, але вони не хочуть перерозподіляти шедеври в експозиції тільки для того, щоб отримати прямий шлях. Їх єдина поступка — тимчасово обміняти місцями два шедеври, якщо це допоможе отримати коротший шлях.

Ви повинні написати програму, яка отримує на вхід розташування експозиції і знаходить найкоротший шлях відповідно до вищезазначених обмежень. Щоб полегшити ваше завдання, куратори вже визначили стандартне розташування. Рисунок 1 показує одне з таких розташувань.

Рисунок 1: Розташування музею

Прогулянка Президента завжди починається від лівої стіни (X = 1, будь-яке $Y$) і закінчується на правій стіні (X = X_\text{max}, будь-яке $Y$). Прогулянка може здійснюватися горизонтально або вертикально; діагональні рухи не дозволені. Роботи даного художника всі позначені однією і тією ж великою літерою ($A$, $B$, $C$ тощо). З Рисунка 1 можна проілюструвати кілька випадків:

1. Якщо президент хоче побачити роботи художника $A$, немає шляху зліва направо. Такий шлях можна отримати, якщо роботу художника $B$ в $(6,6)$ обміняти з роботою художника $A$ з $(1,8)$, $(7,8)$, $(8,8)$, $(10,6)$, $(11,6)$ або $(11,3)$.

2. Якщо президент хоче побачити роботи художника $B$, вже є шлях, що починається в $(1,10)$ і закінчується в $(11,5)$. Коротший шлях можна отримати, якщо роботу $D$ в $(11,7)$ обміняти з роботою художника $B$, наприклад, з $(10,6)$.

3. Якщо президент хоче побачити роботи художника $C$, вже є прямий шлях з $(1,1)$ до $(1,11)$, і коротший шлях не може бути отриманий.

4. Якщо президент хоче побачити роботи $D$, $E$ або $F$, немає можливості отримати шлях зліва направо.