eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Шахматы

Шахматы

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Слон - это шахматная фигура, которая ходит только по диагонали. Известно, что слоны могут добраться только до клеток одного цвета, причем до каждой из них за несколько ходов (считаем что на доске нет других фигур). На доске заданы две клетки. Определить, может ли слон достичь одну из них из другой и каким образом. Координаты в шахматах задаются буквой (от 'A' до 'H') и цифрой (от 1 до 8). Буква задает колонку, а цифра строку доски. Шахматная доска, слон и поля, достижимые за один ход:

prb6032

Вхідні дані

Первая строка содержит количество тестов. Каждый тест начинается со строки, содержащей начальную позицию X и конечную позицию Y. Каждая позиция задается двумя символами, разделенными пробелом. Буква задает колонку, а число строку. Входные данные не содержат одинаковых тестов.

Вихідні дані

Для каждого теста вывести одну строку. Если переместить слона из X в Y за любое число ходов невозможно, то вывести "Impossible". Иначе вывести одну из возможных последовательностей ходов от X до Y. Сначала вывести число ходов n (не более 4). Далее вывести n + 1 позицию, описывающих путь слона. Все символы следует разделять одним пробелом. Существует много решений. Любое из них, содержащее не более 4 ходов, допустимо. Напомним, что ходом называется изменение позиции шахматной фигурой (в нашем случае слоном) согласно шахматным правилам (то есть две соседние позиции в выводимой последовательности должны быть разными).

Приклад

Вхідні дані #1
3
E 2 E 3
F 1 E 8
A 3 A 3
Вихідні дані #1
Impossible
2 F 1 B 5 E 8
0 A 3
Джерело 2013 German Collegiate Programming Contest, Задача C