Вы наткнулись на новый вид шахматной головоломки. Доска, на которой вы играете, не обязательно $$$8 \times 8$$$, но обязательно $$$N \times N$$$. На каждой клетке записано некоторое число от $$$1$$$ до $$$N^2$$$, и все числа попарно различны. В $$$j$$$-й клетке $$$i$$$-й строки записано число $$$A_{ij}$$$.

У вас в распоряжении только три фигуры: конь, слон и ладья. Вначале вы выставляете одну из фигур в клетку с номером $$$1$$$ (вы сами выбираете какую). Далее вы хотите добраться до клетки с номером $$$2$$$ (возможно, проходя через некоторые другие клетки в процессе), далее — до клетки $$$3$$$ и так далее, пока не достигнете клетки $$$N^2$$$. За один шаг вы можете либо сделать один валидный ход текущей фигурой, либо заменить фигуру на другую в вашем распоряжении. Каждая клетка может быть посещена любое количество раз.

Конь может ходить на две клетки по горизонтали и одну по вертикали, либо на две клетки по вертикали и одну по горизонтали. Слон двигается по диагонали. Ладья движется по вертикали или горизонтали. Во время хода фигуры она должна переместиться в клетку, отличную от текущей.

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

Найдите путь, отвечающий всем условиям.