| Codeforces Beta Round 85 (Div. 1 Only) |
|---|
| Закончено |
Маленький Петя любит играть с прямоугольниками. Мама подарила Пете клетчатый прямоугольник размера n × m (n строк, m столбцов). Петя отметил две различные клетки прямоугольника и теперь решает следующую задачу.
Будем называть простым путем между этими клетками последовательность различных клеток a1, a2, ..., ak, где a1 и ak — две отмеченные клетки, при этом ai и ai + 1 являются соседними по стороне клетками пути (1 ≤ i < k). Длиной пути будем называть число k (длину последовательности).
Задача Пети — найти длину самого длинного простого пути, а также вывести сам путь. Помогите ему.
В первой строке через пробел записаны целые числа n и m (4 ≤ n, m ≤ 1000) — количество строк и количество столбцов в прямоугольнике соответственно. Во второй строке через пробел записаны целые числа x1 и y1 — координаты первой отмеченной клетки. В третьей строке через пробел записаны целые числа x2 y2 — координаты второй отмеченной клетки (1 < x1, x2 < n, 1 < y1, y2 < m, x1 ≠ x2, y1 ≠ y2).
Координаты отмеченной клетки — это пара чисел x y, где x обозначает номер строки, а y — номер столбца. Строки нумеруются сверху вниз последовательными целыми числами от 1 до n. Столбцы нумеруются слева направо последовательными целыми числами от 1 до m.
Гарантируется, что отмеченные клетки не находятся в одном столбце или в одной строке.
В первой строке выведите длину найденного пути — k. В последующих k строках выведите k пар чисел, по одной паре в строке — координаты клеток, входящих в найденный путь в порядке следования в пути (путь должен следовать из клетки (x1, y1) в клетку (x2, y2)). Если решений несколько, выведите любое.
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
Рисунок, описывающий тест из условия:
