Змійка

"Змійка" — це аркадна гра, яка ведеться на квадратному полі розміром N \times N, розбитому на клітинки 1 \times 1. Рядки пронумеровані від $1$ до $N$ зверху вниз, а стовпці — від $1$ до $N$ зліва направо. Кожна клітинка має координати $(r,c)$, де $r$ — номер рядка, а $c$ — номер стовпця.

У будь-який момент часу змійка займає послідовність суміжних клітинок, у якій кожні дві сусідні мають спільну сторону. Хвіст змійки знаходиться у першій клітинці цієї послідовності, а голова — в останній. На початку і хвіст, і голова знаходяться в клітинці $(1,1)$, а кожна з інших клітинок містить або ягідку, або грибок.

За хід змійка може перемістити голову в один з чотирьох напрямків: вгору, вліво, вправо, або вниз. Якщо у вибраному напрямку немає клітинки, або в наступній клітинці знаходиться грибок чи частина тіла змійки, змійка гине і гра закінчується. Якщо у клітинці розташована ягідка, змійка її з'їдає і подовжується на одну клітинку. Наприклад, у певний момент гри змійка може мати такий вигляд:

У цій ситуації рух вгору або вниз приводить до загибелі — змійка врізається у власне тіло. Хід праворуч — також до загибелі через грибок. Єдиний безпечний хід — вліво. Після цього ходу змійка набуває такого вигляду:

Мета гравця — керувати змійкою так, щоб вона набрала якомога більшої довжини перед загибеллю. Школяр Василь самостійно грати у "Змійку" не захотів, тому розробив алгоритм управління. Згідно з алгоритмом Василя, перший хід здійснюється вправо, якщо справа немає грибка, або вниз у протилежному випадку (якщо знизу є грибок, змійка гине після першого ходу). Далі змійка намагається рухатися у напрямку попереднього ходу. Якщо це призводить до миттєвої загибелі, вона змінює напрямок на $90$ градусів за годинниковою стрілкою і рухається у новому напрямку (навіть якщо це призводить до загибелі відразу).

Наприклад, нехай поле спочатку виглядає так:

Рухаючись за алгоритмом Василя, змійка безпосередньо перед загибеллю буде мати такий вигляд:

Василь розуміє, що його алгоритм не є оптимальним. Наприклад, у наведеному вище випадку змійка могла б рухатися далі вправо і подовжитись, але за алгоритмом рухається ліворуч і гине. Проте Василь вважає свій алгоритм дуже хорошим і вірить, що він дозволяє змійці досягти великої довжини.

Допоможіть Василю перевірити цю гіпотезу, написавши програму, яка моделює його алгоритм руху. Програма отримує на вхід розмір поля $N$ та координати усіх грибків, і повинна визначити, скільки клітинок займала б змійка безпосередньо перед ходом, на якому вона загине, якщо вона рухається згідно з алгоритмом Василя.