İlan

"İlan" oyunu, N \times N ölçüsündə kvadrat bir sahədə oynanır və bu sahə 1 \times 1 ölçüsündə kvadratlara bölünmüşdür. Sətirlər yuxarıdan aşağıya $1$-dən $N$-ə, sütunlar isə soldan sağa $1$-dən $N$-ə qədər nömrələnmişdir. Hər bir hüceyrə $(r,c)$ koordinatları ilə təyin olunur, burada $r$ sətirin, $c$ isə sütunun nömrəsidir.

Oyun zamanı ilan sahədəki bir neçə bitişik kvadratda yerləşir, yəni ardıcıl hər iki kvadrat qonşudur və ortaq tərəfi var. Ardıcıllığın ilk kvadratında quyruq, sonuncuda isə baş yerləşir. Başlanğıcda həm quyruq, həm də baş $(1,1)$ koordinatındadır, digər bütün hüceyrələrdə isə ya giləmeyvə, ya da göbələk var.

Bir gedişdə ilan başını dörd istiqamətdən birinə — yuxarı, sola, sağa və ya aşağı hərəkət etdirə bilər. Əgər seçilmiş istiqamətdə hüceyrə yoxdursa və ya növbəti hüceyrədə göbələk və ya ilan özü varsa, ilan ölür və oyun bitir. Əgər hüceyrədə giləmeyvə varsa, ilan onu yeyir və uzunluğu bir hüceyrə artır. Məsələn, oyunun bir anında ilan belə ola bilər:

Bu vəziyyətdə yuxarı və aşağı hərəkət edərək ilan öz bədəninə toxunur və ölür. Sağ gedəndə də göbələk olduğu üçün ölür. Yeganə təhlükəsiz gediş sola gedir. Bu hərəkətdən sonra ilan belə görünəcək:

Oyunçunun məqsədi ilanın ölmədən əvvəl mümkün qədər uzun olmasını təmin etməkdir. Məktəbli Vasya "İlan"ı tək oynamağa maraq göstərmirdi, buna görə də bir idarəetmə alqoritmi hazırladı. Vasya'nın alqoritminə görə, ilk gedişdə sağa gedir, əgər sağda göbələk yoxdursa, əks halda isə aşağı (əgər aşağıda göbələk varsa, ilan ilk gedişdən sonra ölür). Sonra isə ilan hər dəfə əvvəlki istiqamətdə irəliləməyə çalışır. Əgər bu, dərhal ölümə səbəb olarsa, istiqaməti saat yönü ilə $90$ dərəcə döndərir və yeni istiqamətdə hərəkət edir (hətta bu zaman dərhal ölsə belə).

Məsələn, sahə ilkin olaraq belə görünür:

Vasya'nın alqoritminə uyğun hərəkət edən ilan, ölmədən əvvəl belə görünəcək:

Vasya başa düşür ki, alqoritmi optimal deyil. Məsələn, yuxarıdakı nümunədə ilan daha da sağa gedib uzunluğunu artıra bilərdi, lakin alqoritmə əsasən sola dönür və ölür. Buna baxmayaraq, Vasya alqoritminin çox yaxşı olduğunu düşünür və onun ilanı böyük uzunluğa çatdıracağına inanır.

Vasya'ya kömək edin və onun alqoritmini modelləşdirən proqram yazın. Proqram $N$ sahə ölçüsünü və bütün göbələklərin koordinatlarını qəbul edir və alqoritmə əsasən, ilan ölməmişdən əvvəl neçə hüceyrəni tutacağını tapır.