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

در مجموع $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.

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

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