Killall

در یک سیستم نرم‌افزاری، تعدادی پردازه در حال اجرا هستند. دو پردازه برای پیش‌برد کار خود ممکن است مستقیما با هم ارتباط برقرار کنند(همه‌ی ارتباط‌ها دو طرفه‌اند). اگر یک پردازه را بکشیم، همه‌ی پردازه‌ها زنده‌ای که در آن لحظه به طور مستقیم یا غیر مستقیم (از طریق یک یا چند پردازه‌ی زنده‌ی میانی) با پردازه‌ی کشته شده ارتباط داشته‌اند، یک پیغام خطا به مدیر سیستم می‌فرستند. می‌خواهیم همه‌ی پردازه‌ها را بکشیم به نحوی که تعداد پیغام خطاهایی که به مدیر سیستم فرستاده می‌شود کمینه شود.

برنامه‌ای بنویسید که:

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

• در سطر اول ورودی، $n$ تعداد پردازه‌ها و $m$ تعداد ارتباط‌های میان‌پزدازه‌ای با فاصله از هم نوشته شده است. پردازه‌ها از ۱ تا $n$ شماره‌گذاری شده‌اند.
• در هر یک از $m$ سطر بعد، دو عدد صحیح $i$ و $j$ ($1\leq i,j \leq n$) با فاصله از هم آمده‌اند که نشان می‌دهد پردازه‌های $i$ و $j$ مستقیما با هم ارتباط دارند. دو پردازه بیش از یک ارتباط مستقیم برقرار نمی‌کنند. یک پردازه با خودش نیز ارتباط برقرار نمی‌کند.

اندازه‌ی ورودی‌هایی که برای نمره‌دهی به برنامه‌ی شما داده می‌شود در جدول زیر آمده است. البته بعضی از این تست‌ها باهم در یک گروه قرار دارند و در مجموع ۲۰ گروه تست وجود دارد.

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

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

• محدودیت زمان: ۳ ثانیه
• محدودیت حافظه: ۱۰۰ مگابایت

• سوال بعد
• سوال قبل