Задача №3861. 8B: кони ходят по очереди

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

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

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

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

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

Примеры
Входные данные
a1
c2
c2
a1
Выходные данные
1 b3
2 a1
1 d4
2 b3
1 c2
2 a1
Сдать: для сдачи задач необходимо войти в систему