المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره‌ی انتخاب تیم:دوره‌ی ۱۴:سوال ۲۰

پسرهای خوب

تعدادی پسر خوب در اجتماع زندگی می‌کنند. دو پسر خوب می‌توانند باهم در ارتباط باشند و اطلاعات خود را رد و بدل کنند. اگر مسیری ارتباطی بین دو نفر وجود داشته باشد، می‌گوییم ارتباط بین آن‌ها برقرار است. دنیای ما با روز صفر آغاز می‌شود. طی روزهای زوج که کارگران در آن سخت مشغول کارند، یک سری ارتباط بین بعضی از دوستان برقرار می‌شود. در روزهای فرد نیز برخی ارتباطات به دلیل فرسایش گسسته می‌شود. لذا ارتباط بین برخی افراد در بعضی اوقات برقرار و در برخی اوقات گسسته می‌شود. برای ما وضعیت ارتباطی بین برخی افراد بسیار حیاتی می‌باشد و باید هرگونه تغییری در آن را یدداشت کنیم. پسرها با شماره‌های ۱ تا $n$ نشان داده می‌شوند.

ورودی

در خط اول فایل ورودی $n$ تعداد پسرهای خوب و $d$ تعداد روزها آمده است. در سطر دوم $k$ تعداد زوج‌های حیاتی و در $k$ سطر بعدی در هر سطر دو عدد نشان‌کر دو نفری می‌باشد که ارتباط بین آن‌ها مهم است، داده شده. در هر یک از $d$ سطر بعدی، اطلاعات یک روز سخت کاری آمده: ابتدا تعداد ارتباطات برقرار شده یا از بین رفته. سپس برای هر ارتباط زمان آن و سپس دو سر آن می‌آید. این زمان‌ها در یک روز متمایز می‌باشند.

دقت داشته‌ باشید که همه‌ی اعداد ورودی به غیر از زمان‌های یک روز، اعداد صحیح در بازه‌ی $[1...500]$ می‌باشند. زمان‌های اعداد صحیح بین ۱ و $10^5$ می‌باشند.

خروجی

در فایل خروجی بدون ترتیب زمانی اتفاقات را ذکر کنید: در هر خط یک تغییر رابطه را به وسیله‌ی چهار عدد $a$، $b$، $c$ و $d$ نشان دهید. $a$ و $b$ به ترتیب روز و زمان تغییر را نشان می‌دهند. $c$ و $d$ دو نفری را که تغییر ارتباط بین آن‌ها اتفاق افتاده را نشان می‌دهد. $c$ باید کوچک‌تر از $d$ باشد.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4 3
1
2 3
2 1 2 3 2 3 4
1 3 2 3
1 5 2 4
1 1 2 3
2 3 2 3
3 5 2 3

ابزار صفحه