Збережіть програмістів Python!#3373
У постапокаліптичній Каліфорнії залишилося лише шість команд програмістів на Python: три команди використовують CPython, а три — Jython. На жаль, вулицями блукають зомбі-програмісти на C++, тому програмісти можуть залишати свої безпечні будинки лише під керівництвом свого доброзичливого диктатора Гвідо.
Шість команд контролюють мережу безпечних будинків, і через обговорення в їхній соціальній мережі Facelessbook вони домовилися обмінятися безпечними будинками — тобто програмісти CPython переїдуть у будинки, зайняті програмістами Jython, і навпаки. Щоночі Гвідо буде вести одну команду з одного безпечного будинку в інший, сусідній, і робитиме це щоночі, поки шість команд не обміняються безпечними будинками.
Кожен безпечний будинок достатньо великий лише для однієї команди, тому жодні дві команди не можуть бути в одному будинку одночасно. Між програмістами CPython і Jython існує величезна недовіра, тому вони наполягають, щоб Гвідо чергував між веденням команди CPython і команди Jython (хоча в першу ніч він може вибрати будь-яку).
Мережа безпечних будинків добре відома, як кількість будинків, так і пари будинків, між якими можна подорожувати за одну ніч. Ваше завдання — визначити мінімальну кількість ночей, необхідну для обміну шістьма командами, якщо це взагалі можливо.
Буде не більше безпечних будинків, кожен з яких ідентифікується однією маленькою літерою. Команди CPython починають у будинках a, b і c; команди Jython починають у будинках d, e і f. Наприкінці обміну команди CPython повинні опинитися в будинках d, e і f, а команди Jython повинні опинитися в будинках a, b і c.
Вхідні дані будуть в одному рядку, який дає з'єднання між будинками. Кожен рядок складатиметься з розділених пробілами "слів". Кожне слово вказує на з'єднання між будинком, представленим першою літерою слова, і будинками, представленими кожною наступною літерою слова.
Для кожного сценарію, якщо є рішення, надрукуйте мінімальну кількість ночей, необхідну для переміщення; якщо немає способу здійснити переміщення, надрукуйте один рядок, що містить No solution.
Перша прикладна головоломка, Рисунок 1, описана як gabd hbcf edf, може бути вирішена за ходи. (Вона представлена тут у розмірі, де ви можете спробувати її вручну, розмістивши пенні на верхньому ряду і нікелі на нижньому ряду, і обмінюючи два ряди відповідно до наведених вище обмежень.)
Рисунок 1: Помірно складна головоломка
Наступна головоломка, показана на Рисунку 2, описана як bacgh dge feh, вимагає ходів.
Рисунок 2: Складніша головоломка
Ситуація, зображена на Рисунку 3, gab hbdf ibc edf, вимагає ходів.
Рисунок 3: Удачі з цим!
Приклад 1
Примітка: Цю головоломку створив Боб Херн у Дартмуті.