کوسه و تمساح‌ها


کوسه در یک باغ پسته‌ی بزرگ به شکل یک مربع n×nn\times n گیر افتاده است. در این باغ mm تمساح حضور دارند. کوسه پس از دیدن عکس زیر، تصمیم گرفته با تمساح‌ها رودررو نشود. اکبر بر علیه مصباح کوسه در حال حاضر می‌داند که هر تمساح کجاست. وی همچنین می‌داند که در هر لحظه خودش و تمساح‌ها می‌توانند حداکثر یک واحد به یکی از چهار جهت حرکت کنند یا سر جای خود ثابت بمانند. اما کوسه به دلیل درخت‌های باغ پسته در لحظه‌های بعدی نمی‌تواند موقعیت تمساح‌ها را ببیند. وی همچنین می‌داند که بین بعضی خانه‌های باغ - نه روی حاشیه‌ها - دیوار وجود دارد تا جلوی پسته‌دزدها گرفته شود، و نه کوسه و نه تمساح‌ها نمی‌توانند از دیوارها رد شوند. وی می‌خواهد طوری حرکت کند که هیچ‌گاه امکان نداشته باشد با یک تمساح در یک خانه قرار بگیرد. حال کوسه می‌خواهد طوری حرکت کند که هرطور که تمساح‌ها حرکت کنند وی موفق شود که از جدول خارج شود. اما تمساح‌ها می‌خواهند جلوی وی را بگیرند و ممکن است طوری حرکت کنند که وی موفق نشود، و در این صورت کوسه می‌خواهد مدت زمان بیشتری از رودررو شدن با تمساح‌ها اجتناب کند. به کوسه کمک کنید بداند که آیا موفقیتش تضمینی است یا نه؟ و این‌که اگر موفقیتش تضمینی نیست، حداکثر چقدر زنده خواهد ماند؟

ورودی🔗

در خط اول n103n\leq 10^3 ابعاد جدول و mn2m\leq n^2 تعداد تمساح‌ها می‌آید. در خط بعدی 1x,yn1\leq x,y\leq n مختصات کوسه می‌آید. در mm خط بعدی مختصات تمساح iiام می‌آید. سپس دو جدول n×nn\times n می‌آید. در جدول اول خانه‌ی i,ji,j صفر است اگر دیواری در سمت راست آن وجود داشته باشد و در غیر این صورت یک است. در جدول دوم خانه‌ی i,ji,j صفر است اگر دیواری در سمت بالای آن وجود داشته باشد و در غیر این صورت یک است.

خروجی🔗

اگر کوسه می‌توانست خارج شود باید عبارت "Ma Ahle Koose Nistim" چاپ شود و در غیر این صورت اولین زمانی که مستقل از حرکت کوسه، تمساح‌ها بتوانند طوری حرکت کنند که او را بگیرند را چاپ کنید. تضمین می‌شود که حتما یکی از دو حالت فوق رخ می‌دهد، یعنی ممکن نیست که کوسه نه به تمساح‌ها برسد نه به بیرون زمین.

مثال🔗

ورودی نمونه ۱

3 4
2 2
1 1
1 3
3 1
3 3
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
Plain text

خروجی نمونه ۱

2
Plain text

ورودی نمونه ۲

3 7
2 2
1 1
1 3
2 1
2 3
3 1
3 2
3 3
0 0 1
1 1 1
1 1 1
1 1 1
1 1 1
1 1 1
Plain text

خروجی نمونه ۲

Ma Ahle Koose Nistim
Plain text

توضیح🔗

در مثال اول در ثانیه‌ی اول در همه‌ی خانه‌ها به جز خانه‌ی کوسه ممکن است تمساح باشد پس کوسه سر جای خود می‌ماند. در ثانیه‌ی بعدی حضور تمساح در همه‌ی خانه‌ها ممکن است پس در این ثانیه تمساح ها مستقل از حرکت کوسه می‌توانند او را بگیرند.

برای نمونه‌ی دوم به شکل زیر دقت کنید. کوسه در حرکت اول یک واحد و در حرکت دوم یک واحد دیگر به سمت بالا حرکت می‌کند و از جدول خارج می‌شود. توضیح تصویر