Один из источников новых задач — игры. Надо выбрать игру и сосредоточиться на какой-то части механики игры. Так получится неплохая задача.
Давайте попробуем. Puzzle and Dragon стала популярной игрой в Японии — мы сосредоточимся только на части механики игры, в которой нужно передвигать сферы на доске.
(Картинка со странички Википедии: http://en.wikipedia.org/wiki/Puzzle_&_Dragons)Задана доска размера n × m, в каждой ячейке доски находится сфера. Во время игры разрешено совершать следующие ходы. В начале хода вы прикасаетесь к одной из ячеек на доске, затем вы передвигаете палец в одну из соседних ячеек (у ячейки, которая не находится на границе, 8 соседей), затем вы можете еще раз передвинуть палец из текущей ячейки в одну из соседних и так далее. Каждый раз, когда вы двигаете палец от одной ячейки к другой, сферы, находящиеся в этих ячейках, меняются местами. Иными словами, какие бы движения пальцем вы не сделали, сфера в той клетке, к которой вы прикасаетесь, никогда не поменяется.
Задача игрока в игре — достичь такого расположения сфер, при котором сферы пропадут, а герой сможет атаковать врага — но эти детали нам не важны. Мы фокусируемся на другом. Пусть задано начальное расположение сфер, и конечное расположение сфер. Ваша задача — определить, можно ли получить из начального расположения конечное за один ход.
Выходные данные
Если решения не существует, выведите: -1.
Если решение существует, то выведите в первой строке целое число k (1 ≤ k ≤ 106) — количество движений пальца в вашем ходе.
В следующей строке выведите два целых числа x0 и y0 (1 ≤ x0 ≤ n; 1 ≤ y0 ≤ m) — положение ячейки, к которой вы прикоснетесь в начале. В каждой из следующих k строк выведите два целых числа xi и yi (1 ≤ xi ≤ n; 1 ≤ yi ≤ m) — ячейка, в которую вы передвигаете палец в данный момент. Обратите внимание, что эта ячейка должна быть соседней с предыдущей, другими словами max(|xi - xi - 1|, |yi - yi - 1|) = 1.
Если у задачи несколько решений, можно вывести любое. Можно доказать, что при указанных ограничениях, если существует решение, то существует и решение с не более, чем 106 операциями.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 2
1 3
2 3
1 3
3 2
|
3
1 1
2 2
2 1
1 1
|
|
2
|
2 2
1 3
2 3
1 2
2 3
|
-1
|
|
3
|
1 4
1 2 3 4
4 3 2 1
|
-1
|
|
4
|
4 1
1
2
3
4
3
1
2
4
|
2
3 1
2 1
1 1
|