المپدیا

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

ابزار کاربر

ابزار سایت


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

Ring

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

در مجموع $k$ تا یار بودن که هر کدوم سر از یکی از $k$ تا غار در آوردن. هر کدوم از این غارها تشکیل شده از یک سری حفره و یک سری دالان. هر دالان دوتا از حفره‌ها رو به هم متصل می‌کنه و از هر جهت کی طی‌اش کنید ثانیه طول می‌کشه. می‌دونیم که غار $i$ام، $n_i$ تا حفره داره و در اثر طلسم سارون یار $i$ام سر از حفره‌ي اول این غار در آورده. در ضمن می‌دونیم که اگر همه‌ی یارها در یک زمان در حفره‌ی آخر غارشون باشن، طلسم شکسته می‌شه؛ ولی چون یاران حلقه عجله دارن که هرچه سریع‌تر به هم برسن، نمی‌تونن در هیچ حفره‌ای توقف کنن. ضمن دالان‌ها خیلی تنگن و وقتی از یک سرش را افتادین یک ثانیه‌ی بعد باید به سر دیگرش برسین، وگرنه خفه می‌شین؛ وسط یک دالان هم نمی‌شه جهت حرکت رو تغییر داد.

شما باید برنامه‌ای بنویسید که با گرفتن شکل غار‌‌ها سریع‌ترین زمانی رو که یاران می‌تونن طلسم رو به پایان برسونن، رو اعلام کنه.

ورودی

سطر اول ورودی حاوی تعداد یارها یعنی $k$ است. در هر یک از $k$ بلوک بعد توصیف یک غار آمده است. در سطر اول بلوک $i$ام نخست، $n_i$، تعداد حفره‌های غار $i$ام و سپس تعداد دالان‌های آن، یعنی $m-i$، آمده است؛ می‌دانیم که $m-i \leq \binom{n}{2}$ می‌باشد. در هر یک از $m_i$ سطر بعدی دو سر یکی از $m_i$ دالان غار $i$ام نوشته شده است.

در ۷۰ درصد از موارد آزمون، $k\leq 10$ و $n \leq 50$ است و در ۳۰ درصد دیگر $k\leq 30$ و $n\leq 500$ می‌باشد. در ضمن در این ۳۰ درصد، زمان مجاز برای هر مورد ۱۵ ثانیه می‌باشد!

خروجی

در صورتی که یاران می‌توانند از طلسم‌ رهایی یابند، در تنها سطر خروجی کوتاه‌ترین زمانی که این کار در آن ممکن است را بنویسید و اگر نمی‌توانند در تنها سطر خروجی بنویسید Impossible.

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
2
3 2
1 2
3 2
4 3
1 2
2 3
3 4
6
2
2 1
1 2
3 1
1 2
Impossible

ابزار صفحه