410751: GYM104096 C Путешествие шахматного коня

C. Путешествие шахматного коняограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Начинающий шахматист Вася исследовал возможные движения шахматного коня по шахматной доске ($$$8\times 8$$$ клеток): его конь начал движение с некоторой клетки с номером строки $$$x$$$ и номером столбца $$$y$$$ и совершил $$$n$$$ ходов по правилам шахматного коня (шахматный конь ходит буквой «Г»: за один ход он совершает прыжок или на одну клетку по горизонтали и одновременно на две клетки по вертикали, или на две клетки по горизонтали и одновременно на одну клетку по вертикали, в обоих случаях прыжок по горизонтали и по вертикали может совершаться в любом направлении). Вася старательно записывал координаты каждой клетки, которую посещал конь после очередного хода. Но в какой-то момент он увлёкся и забыл записать ход, поэтому в его записях оказались координаты только $$$n-1$$$ клетки. Вася уверен, что все остальные клетки он записал корректно и теперь по своим записям хочет восстановить номер пропущенного хода и координаты клетки, в которой мог оказаться конь после этого хода.

Входные данные

В первой строке входных данных записано единственное число $$$n$$$ — количество ходов ($$$2 \leq n \leq 100$$$). В следующей строке записаны два целых числа: $$$x$$$ и $$$y$$$ — номер строки и номер столбца исходной клетки ($$$1 \leq x, y \leq 8$$$). В последующих $$$n-1$$$ строках приведены записи Васи ходов коня: в каждой строке указан номер строки и номер столбца клетки, в которой оказался конь после очередного хода. Порядок записей соответствует порядку посещения клеток конем с учётом того, что запись об одном из ходов отсутствует. Гарантируется, что записи приведены корректно, то есть действительно конь мог совершить такое движение по указанным клеткам с учётом пропуска в записях одной из клеток.

Выходные данные

В первой строке вывода необходимо записать номер хода, данные о котором потеряны (ходы нумеруются с 1). Во второй — пару целых чисел: номер строки и номер столбца клетки, в которой оказался конь после потерянного хода. В случае нескольких вариантов ответа можно вывести любой из них.

ПримерыВходные данные

3
1 1
3 2
2 5

Выходные данные

2
1 3

Входные данные

3
3 3
3 3
1 4

Выходные данные

1
1 2