Маленький Петя любит играть с прямоугольниками. Мама подарила Пете клетчатый прямоугольник размера n × m (n строк, m столбцов). Петя отметил две различные клетки прямоугольника и теперь решает следующую задачу.
Будем называть простым путем между этими клетками последовательность различных клеток a1, a2, ..., ak, где a1 и ak — две отмеченные клетки, при этом ai и ai + 1 являются соседними по стороне клетками пути (1 ≤ i < k). Длиной пути будем называть число k (длину последовательности).
Задача Пети — найти длину самого длинного простого пути, а также вывести сам путь. Помогите ему.
Выходные данные
В первой строке выведите длину найденного пути — k. В последующих k строках выведите k пар чисел, по одной паре в строке — координаты клеток, входящих в найденный путь в порядке следования в пути (путь должен следовать из клетки (x1, y1) в клетку (x2, y2)). Если решений несколько, выведите любое.
Примечание
Рисунок, описывающий тест из условия:
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 4
2 2
3 3
|
15
2 2
1 2
1 1
2 1
3 1
4 1
4 2
4 3
4 4
3 4
2 4
1 4
1 3
2 3
3 3
|