Задачі
Найкоротший шлях двох коней
Найкоротший шлях двох коней
Переведіть кожного з двох коней з однієї клітинки в іншу за найменшу загальну кількість ходів. Два коня не можуть одночасно знаходитись в одній клітинці.
\InputFile
Спочатку записані координати першого та другого коня, потім координати клітинок, куди потрібно їх перемістити.
\OutputFile
Вивести послідовність ходів коней у вигляді декількох рядків. Першим символом у рядку повинен бути номер коня (\textbf{1} або \textbf{2}), потім, через пропуск, координати клітинки, у яку він переставляється. Необхідно вивести довільний з можливих оптимальних розв'язків.
Вхідні дані #1
a1 c2 c2 a1
Вихідні дані #1
1 b3 1 d4 2 a1 1 c2