F. Голодный конь

На доске $N \times N$ в клетке $(x_1, y_1)$ стоит шахматный конь. Он хочет попасть в клетку $(x_2, y_2)$ за наименьшее число ходов.

Выведите это число и сам маршрут. Маршрутов может быть несколько; выведите лексикографически наименьший как последовательность пар координат.

Граф здесь неявный: вершины — клетки, рёбра — ходы коня. Ни списка смежности, ни матрицы строить не надо.

Одна строка содержит пять чисел: $N$ ($5 \le N \le 20$), $x_1$, $y_1$, $x_2$, $y_2$ ($1 \le x_1, y_1, x_2, y_2 \le N$).

Левая верхняя клетка имеет координаты $(1, 1)$.

В первой строке — наименьшее число ходов $K$.

В следующих $K + 1$ строках — координаты клеток маршрута, начиная со стартовой.