در کتیبه‌هایِ باستانیِ کشف شده از حفّاری‌هایِ تخت جمشید، چنین نوشته شده است که:

۲۰۰۸‎ سال پیش از میلاد مسیح (این‌‎که چه‌جوری حدس زدند که ‎۲۰۰۸‎ سال بعدش ‎«میلاد مسیح‎» می‌شه، بماند!)، المپیاد جهانی فامپیوتر (هنوز معلوم نیست این المپیاد چی‌چی بوده) قرار بوده در کشور «فصر» (یک کشور نه‌چندان‌افسانه‌ای که پایتختش فاهره بوده است‎!‎) برگزار شود.

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

این پل باید دقیقاً بین یک شهر از مملکت پارسیان و یک شهر از ممکلت فصر ساخته شود و مصالح لازم برای ساختن پل (نظیر آهن و بتون) باید به‌سرعت تهیه شوند.

پادشاه بزرگ پارسیان، به پارسا (معمار مخصوص دربار) اجازه داده است تا برای ساختن این پل و ایجاد یک راه از پارسه به فاهره، هر چند تا از جاده‌های مملکت پارسیان را که لازم‌ست خراب کرده و از مصالح آن برای ساختن پل استفاده کند. پادشاه فصر نیز این اجازه را در مورد تمام جاده‌های مملکت فصر به پارسا داده است (‎چه اهمّیّتی‎!‎)

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

به بیان ساده‌تر، هر یک از دو مملکت پارسیان و فصر یک مؤلفه از یک گراف ساده و بدون وزن هستند. می‌خواهیم دقیقاً یک یال (بدون وزن) بین یکی از شهرهای مؤلفه‌ی پارسیان و یک از شهرهای مؤلفه‌ی مصر اضافه کنیم به‌طوری‌که اوّلاً، بین پارسه (یک رأس خاص از مؤلفه پارسیان) و فاهره (یک رأس خاص از مؤلفه فصر) یک مسیر به‌وجود بیاید؛ ثانیاً هزینه‌ی ساخت پل (هزینه یال اضافه شده) منهای تعداد یال‌هایی که در یک مسیر ایجادشده بین پارسه و فاهره قرار ندارند (و بالطبع می‌توانند تخریب شده و ‎«یک واحد‎» مصالحشان مورد استفاده‌ی مجدّد قرار بگیرند)، بیشینه بشود.

• در سطر اوّل ورودی، ‎$n$‎، تعداد کل رئوس گراف (مجوع تعداد شهرهای دو مملکت پارسیان و فصر) آمده است. فرض می‌کنیم شماره رئوس از صفر تا ‎$n-1$‎ است و رأس صفر همیشه پارسه و رأس ‎$n-1$‎ همیشه فاهره است.
• در سطر دوم تا ‎$n+1$،‎اُم ورودی، در سطر ‎$2\le i\le n+1$‎، ابتدا تعداد همسایه‌های رأس ‎$i-2$،‎اُم ‎($d_{i-2}$)‎ و سپس شماره‌ی هر کدام از این ‎$d_{i-2}$‎ همسایه با یک فاصله بین‌شان آمده است.
• در سطر ‎$n+2$‎، تعداد پل‌های قابل احداث ‎$p$‎ نوشته شده است.
• نهایتاً در سطرهای ‎$n+3$‎ تا ‎$n+p+2$‎، در هر سطر مشخّصات یک پل نوشته شده است. پل ‎$j$‎ با ‎۳‎ عدد ‎$v_j~u_j~c_j$‎ نمایش داده می‌شود که ‎$v_j$‎ و ‎$u_j$‎ شماره‌ی رئوس دو سر پل و ‎$c_j$‎ هزینه‌ی ساختن پل است.
• $2 \le n \le 2008$‎ و ‎$0 \le p \le 200008$‎.
• تمام ‎$c_j$‎ ها صحیح، مثبت و کوچک‌تر از ‎$10^9$‎ هستند.
• تضمین می‌شود که در گراف ورودی اوّلیه، بین رأس ‎$0$‎ و رأس ‎$n-1$‎ مسیر وجود ندارد.

• در تنها سطر خروجی، حداکثر میزان مصالح باقی‌مانده در پایان عملیّات ‎(سود)‎ را بنویسید. در صورتی که میزان مصالح موردنیاز منهای تعداد یال‌هایی که حذف می‌شوند، در بهترین حالت، عددی منفی است (به‌معنی نیاز برای خرید مصالح اضافه از یک کشور بیگانه) این کم‌ترین هزینه را (به‌صورت همان عدد منفی) بنویسید.
• در صورتی که با احداث هیچ‌کدام از پل‌ها مسیری از پارسه به فاهره ایجاد نمی‌شود، در تنها سطر خروجی عبارت No Solution‎ را (عیناً با ‎N‎ و S‎‎ بزرگ) چاپ کنید.

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

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