- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
سال‌ها از مرگ دردناک و مظلومانه‌ی کاراکتر اصلی ۱ گذشت، در متن وصیت‌نامه‌ی آن مرحوم آمده بود که دوست دارم پسرم هم کاراکتر اصلی بشود و نه یک کاراکتر کمکی. پسرِ کاراکتر اصلی ۱ نیز مثل کاراکترهای کمکیِ شاگرد پدرش از هندسه متنفر بود اما به‌شدت به درس شیمی علاقه‌مند بود، به همین علت مدرس درس شیمی در دانشگاه شد و کاراکتر اصلی ۲ نام گرفت. از قضا شاگردان پدرش نیز در دانشگاه، شدند شاگردان او در درس شیمی!
دانشگاه‌ها به‌تازگی آغاز به کار کرده‌اند و کاراکتر اصلی ۲ می‌خواهد در همین ترم اول دانشگاه انتقام پدرش را بگیرد و با کاراکترهای کمکی بی‌حساب بشود پس آن‌چنان سوال سختی برای امتحان شیمی آن‌ها طرح کرده که روح پدرش به آرامش برسد! سوال این است:
تعداد $n$ اتم داریم (شماره‌گذاری شده از ۱ تا $n$) که بعضی از آن‌ها باهم پیوند داده‌اند، می‌دانیم هر پیوند فقط بین ۲ اتم شکل می‌گیرد. هم‌چنین درباره‌ی اتم‌های داده شده می‌دانیم فقط ۲ نوع پیوند میان این اتم‌ها ممکن است، پیوندهای شُل و پیوندهای سفت.
در ابتدا همه‌ی پیوندها از نوع شُل هستند. وسیله‌ای داریم که قادر است نوع پیوند میان دو اتم را از شُل به سفت تغییر دهد. از دیگر قابلیت‌های این وسیله، نمایش‌گری است که اندازه‌ی بزرگترین زیرمجموعه‌ی خفن از مجموعه‌ای از اتم‌ها که به آن دادیم را پس از هربار عمل سفت‌سازی (تغییر پیوند میان دو اتم از شل به سفت) نشان می‌دهد.
زیرمجموعه‌ی خفن یعنی زیرمجموعه‌ای از اتم‌ها که بین هر دو اتم از این زیرمجموعه رابطه‌ی طلایی وجود نداشته باشد.
همان‌طور که می‌دانید الکترون‌ها می‌توانند با استفاده از پیوند بین دو اتم بین این دو اتم جابجا شوند.
دو اتم رابطه‌ی طلایی دارند اگر و تنها اگر یک الکترون بتواند با جابجایی بین اتم‌ها با استفاده از پیوندهای بینشان از یکی به آن‌یکی برسد طوری که از هیچ پیوندی دوبار استفاده نکند و حداقل از یک پیوندِ سفت، استفاده کند. (دقت کنید ممکن است الکترون چند بار از یک اتم استفاده کند اما چندبار از یک پیوند استفاده نمی‌کند)
مدتی است نمایش‌گر وسیله خراب شده است به همین دلیل جزئیات اعمال سفت‌سازی (تغییر پیوند میان دو اتم از شل به سفت) انجام شده را در اختیار شما قرار می‌دهیم و شما باید اندازه‌ی بزرگترین زیرمجموعه‌ی خفن از مجموعه‌ی داده شده اتم را پس از هربار عمل سفت‌سازی محاسبه کنید.
از آن‌جایی که هیچ‌کدام از کاراکترهای کمکی در امتحان قادر به حل این سوال نیستند. کاراکتر اصلی ۲ در جهت آرامش بیش‌تر پدرش تصمیم گرفت این سوال را برای تیم طراحی سوالات این مسابقه ارسال کند تا ما آن را در بین سوالاتمان قرار دهیم. حال برنامه‌ای بنویسید که با محاسبه‌ی درست پاسخ آرامش را از روح کاراکتر اصلی ۱ بگیرد.
ورودی
در خط اول ورودی سه عدد طبیعی $n$، $m$ و $q$ به ترتیب نشان‌دهنده‌ی تعداد اتم‌ها، تعداد پیوندها و تعداد دفعات انجام عمل سفت‌سازی، داده می‌شوند.
در $m$ خط بعدی و در هر خط دو عدد طبیعی $v$ و $u$ داده می‌شوند که شماره‌ی دوتا از اتم‌ها هستند که میان آن‌ها یک پیوند وجود دارد. (پیوندها به ترتیب داده شدن از ۱ تا $m$ شماره‌گذاری شده اند.)
در $q$ خط بعدی و در هر خط یک عدد طبیعی داده می‌شود که شماره‌ی پیوندی است که دستگاه روی آن عمل سفت‌سازی انجام می‌دهد. تضمین می‌شود قبل از این هیچ‌گاه روی این پیوند عمل سفت‌سازی انجام نشده است.
$$1 \leq n, m, q \leq 100 \ 000$$ $$1 \leq v, u \leq n$$
خروجی
در $q$ خط اندازه‌ی بزرگترین زیرمجموعه‌ی خفن را پس از $q$ بار انجام عمل سفت‌سازی چاپ کنید.
مثال
ورودی نمونه
4 4 1
1 2
2 3
3 1
3 4
1
خروجی نمونه
1
توضیح
پس از آنکه پیوند بین دو اتم ۱ و ۲ سفت می‌شود، از بین چهار اتم ۱ و ۲ و ۳ و ۴، بین هر دوتایی رابطه طلایی یافت می‌شود؛ بنابراین از بین این چهار اتم حداکثر یک اتم می‌تواند در مجموعه خفن باشد.
ارسال پاسخ برای این سؤال