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

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

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

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

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

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