eolymp
Competitions

11.02 Старшая лига

Кратчайший путь двух коней

Переведите каждого из двух коней из одной клетки в другую за наименьшее общее число ходов. Два коня не могут одновременно находиться в одной клетке.

Входные данные

Сначала записаны координаты первого и второго коня, затем координаты клеток, куда нужно их переместить.

Выходные данные

Вывести последовательность ходов коней в виде нескольких строк. Первым символом в строке должен быть номер коня (1 или 2), затем, через пробел, координаты клетки, в которую он переставляется. Необходимо вывести любое из возможных оптимальных решений.

Time limit 1 second
Memory limit 64 MiB
Input example #1
a1
c2
c2
a1
Output example #1
1 b3
1 d4
2 a1
1 c2