Шахи#6032
Слон — це шахова фігура, яка рухається лише по діагоналі. Відомо, що слони можуть потрапити лише на клітинки одного кольору, і до кожної з них можна дістатися за кілька ходів (вважаємо, що на дошці немає інших фігур). На дошці задано дві клітинки. Потрібно визначити, чи може слон дістатися з однієї клітинки до іншої, і якщо так, то яким чином. Координати в шахах задаються літерою (від '' до '') і цифрою (від до ). Літера вказує на колонку, а цифра — на рядок дошки. Шахова дошка, слон і поля, досяжні за один хід:
Перший рядок містить кількість тестів. Кожен тест починається з рядка, що містить початкову позицію і кінцеву позицію . Кожна позиція задається двома символами, розділеними пробілом. Літера вказує на колонку, а число — на рядок. Вхідні дані не містять однакових тестів.
Для кожного тесту вивести один рядок. Якщо перемістити слона з в за будь-яку кількість ходів неможливо, то вивести "Impossible". Інакше вивести одну з можливих послідовностей ходів від до . Спочатку вивести число ходів (не більше ). Далі вивести n + 1 позицію, що описують шлях слона. Усі символи слід розділяти одним пробілом. Існує багато рішень. Будь-яке з них, що містить не більше ходів, допустиме. Нагадаємо, що ходом називається зміна позиції шаховою фігурою (у нашому випадку слоном) згідно з шаховими правилами (тобто дві сусідні позиції у виведеній послідовності повинні бути різними).
Приклад 1