اپدیا

دزدان دریایی کاراییب در زندانی قرار دارند که به شکل جدولی $n \times n$ است. از آنجایی که جک در جوانی المپیاد کامپیوتری بوده کامپیوتر مرکزی زندان را هک کرده و متوجه شده است که اتاق آن ها در خانه $(1, 1)$ جدول و در خروجی زندان در خانه $(n, n)$ قرار دارد.

هر کدام از خانه‌های جدول یک اتاق است که چهار در دارد که هر کدام روی یکی از ضلع‌های مربع هستند.

جک بعد از هک کردن کامپیوتر مرکزی متوجه شد که بعضی از خانه‌های جدول مین گذاری شده‌اند. طبعا هیچ‌کس دوست ندارد از روی مین رد بشود. حالا مسئله این است که جک می‌خواهد گروهش را به بیشترین تعداد دسته ممکن افراز کند و هر گروه از یک مسیر جدا برود. به این معنی که جک نیاز دارد بیشترین تعداد مسیر فرار ممکن را بداند به طوریکه هیچ اتاقی در دو مسیر دیده نشود (به جز اتاق شروع و پایان). و البته واضح است که این بیشترین تعداد مسیر ممکن حداکثر ۲ هست.

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

جک طی تحقیقاتش فهمید که مشتلی مسئول زندان است. همه ما می‌دانیم که جک و مشتلی از زمان المپیادشان تا الان دشمنان خونین همدیگر هستند. بنابراین مشتلی برای اینکه اطمینان حاصل کند جک از زندان فرار نمی‌کند به شایان دستور داد که هرگونه ارتباط از داخل زندان به خارج را ببندد و شایان نیز چنین کرد ولی از آنجایی که قبلا از جک رشوه گرفته بود ارتباط از خارج زندان به داخل را نبست!

بنابراین جک نمی‌تواند مختصات مین‌ها را برای شما بفرستد پس از شما می‌خواهد تابعی پیاده سازی کنید که جواب مسئله را بدهد. یعنی در این سوال شما اجازه خواندن از ورودی یا نوشتن در خروجی را ندارید. شما باید توابع زیر را پیاده سازی کنید و جک از آن‌ها استفاده می‌کند. همچنین برنامه شما نباید تابع main داشته باشد.

در صورت هرگونه تلاش برای خواندن از ورودی یا نوشتن در خروجی یا استفاده از تابع exit نمره شما صفر می‌شود.

• void init(int n, int q)

شما باید این تابع را پیاده‌سازی کنید. در ابتدای فرایند این تابع تنها یک بار صدا زده می‌شود و مقادیر $n, q$ را به شما می‌دهد.

• n: اندازه طول و عرض زندان
• q: تعداد بار‌های فراخوانی تابع bomb

• int bomb(int x, int y)

شما باید این تابع را پیاده‌سازی کنید. جک با صدا زدن این تابع به شما مختصات یک مین جدید را می‌دهد. خروجی این تابع باید بیشترین تعداد مسیر فرار ممکن با اطلاعات فعلی باشد.

ارزیاب نمونه در خط اول اعداد $n,q$ را به ترتیب می‌خواند.

سپس $q$ خط دیگر می‌خواند که در هر کدام ابتدا عدد $x$ و سپس $y$ آمده است. هر خط نشان دهنده‌یک کوئری انفجار مین است.

• زیرمسئله اول (۲ نمره): $n \le 4$
• زیرمسئله دوم (۵ نمره): $n \le 10$
• زیرمسئله سوم (۱۳ نمره): $n \le 100$
• زیرمسئله چهارم (۳۱ نمره): اولین کوئری $x=1,y=2$ است.
• زیرمسئله پنجم (۷ نمره): ناحیه مین‌گذاری شده همبند است.
• زیرمسئله ششم (۱۸ نمره): ناحیه مین‌گذاری شده حداکثر $10$ مولفه همبندی دارد.
• زیرمسئله هفتم (۲۴ نمره): بدون محدودیت اضافی

• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت
• $2 \leq n \leq 3000$
• $1 \leq q \leq min(2\times10^5, n^2-2)$
• $1 \leq x,y \leq n$
• تضمین می‌شود که $x,y$ ها غیر‌تکراری هستند. همچنین خانه شروع و پایان هیچوقت مین‌گذاری نمی‌شوند.