На шахматной доске NxN в клетке (x1,y1) стоит голодный шахматный конь. Он хочет попасть в клетку (x2,y2), где растет вкусная шахматная трава. Какое наименьшее количество и каких ходов он должен для этого сделать?
Формат входных данных
Входной файл содержит пять чисел: N,x1,y1,x2,y2 (5<=N<=15,
1<=x1,y1,x2,y2<=N).
Левая верхняя клетка доски имеет координаты (1,1), правая нижняя - (N,N).
Формат выходных данных
Первая строка выходного файла должна содержать единственное число K - наименьшее
необходимое число ходов коня. В каждой из следующих K+1 строк должно быть записано 2 числа -
координаты очередной клетки в пути коня.
Пример
| Пример ввода | Пример вывода |
5 1 1 3 1 |
2 1 1 2 3 3 1 |