المپدیا

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

ابزار کاربر

ابزار سایت


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

Capture

در کشور شرکینافاسو ‎$n$‎ شهر با شماره‌های ‎$1$‎ تا ‎$n$‎ و تعدادی جاده که همه دوطرفه هستند بین این شهرها قرار دارند. در شهر شماره‌ی ‎$a$‎ آذوقه‌ی کل کشور نگه‌داری می‌شود. همچنین می‌دانیم نظامیان دشمن در شهر شماره‌ی ‎$b$‎ پایگاهی زیرزمینی بنا کرده‌اند.

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

محاسبات نیروهای اطلاعاتی نشان داده است که نیروهای دشمن می‌توانند با انتخاب کوتاه‌ترین مسیر، دقیقاً پس از ‎$t$‎ ساعت خود را از پایکاه زیرزمینی به انبار آذوقه برسانند. اما محاسبات ستاد پشتیبانی نشان می‌دهد که برای خارج کردن تمام آذوقه از انبار جهت انتقال به جای امن ‎$t+1$‎ ساعت زمان نیاز می‌باشد.

وظیفه‌ی شما این است که با داشتن نقشه‌ی کشور و شهرهای ‎$a$‎ و ‎$b$‎ کم‌ترین تعداد جاده‌ای را پیدا کنید که با خراب کردن آن‌ها کم‌ترین زمان برای رسیدن از شهر ‎$a$‎ به شهر ‎$b$‎ حداقل یک ساعت افزایش می‌یابد.

فرض کنید در ابتدای کار با استفاده از جاده‌ها می‌توان از شهر ‎$a$‎ به شهر ‎$b$‎ رسید.

ورودی

  • سطر اول ورودی سه عدد ‎$n$‎، ‎$a$‎، و ‎$b$‎ به ترتیب آمده است.
  • در ‎$n-1$‎ سطر بعدی نیمه‌ی پایین گراف مجاورت نقشه‌ی کشور آمده‌است. بدین صورت که اگر سطر ‎$i$‎ و ستون ‎$j$‎ شامل عدد ‎$1$ (یا$0$)‎ بود، بین شهر ‎$i$‎ و شهر‎$j$‎ جاده مستقیم وجود دارد (ندارد).
  • ‎$2\leq n \leq400$‎

خروجی

  • در خروجی در سطر اول تعداد جاده‌هایی که باید حذف شوند ‎($k$)‎ را بنویسید.
  • در ‎$k$‎ سطر بعدی در هر سطر دو عدد بنویسید که شماره‌ی دو شهر دو طرف جاده‌ای هستند که باید حذف شود.
  • در صورتی که مساله جواب نداشت، در تنها سطر خروجی عبارت ‎Impossible‎ را چاپ کنید.

محدودیت‌ها

  • محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

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

ورودی نمونه خروجی نمونه
4 1 4‎
1‎
1 0‎
0 1 1
2‎
1 2
1 3

ابزار صفحه