Задача "Еще один конь"

На шахматной доске 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