المپدیا

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

ابزار کاربر

ابزار سایت


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

مافیا

یک بنگاه مافیایی در نظر دارد بر ضد یک عضو سابق خود پرونده‌سازی کند. در پرونده‌ی این عضو در حال حاضر $n$ موضوع مطرح است، در ضمن $d$ عضو این باند هر کدام قادر به پرونده‌سازی و ایجاد ارتباط بین دو موضوع پرونده در قبال مقدا مشخصی دست‌مزد هستند. مضنون در صورتی محکوم می‌شود که تمام موضوعات پرونده به هم مربوط شوند. با توجه به وضع بد اقتصادی و پایین آمدن سود‌دهی این بنگاه، بنگاه مورد نظر تصمیم به «بازخرید» کردن حداکثر تعداد اعضای خود گرفته است به طوری که هر فردی که به هیچ نحوی نتوان از او برای ساختن پرونده‌ی حاضر با کم‌ترین هزینه استفاده کرد فردا شب «بازخرید» خواهد شد. شما باید لیستی از افرادی که بازخرید خواهند شد تشکیل دهید.

ورودی

در سطر اول فایل ورودی $n$ و $d$ و در $d$ سطر بعد در هر سطر نخست شماره‌ی دو موضوعی که این عضو قادر به مربوط کردن آن‌هاست و سپس دستمزد وی آمده است. (مقدار $n$ حداکثر $10^4$، مقدار $d$، $10^6$ است.

خروجی

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

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

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

ابزار صفحه