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

به گفته‌ی یکی از مسئولین، نیروهای امدادی خیکولند به سرعت تعدادی جاده‌‌ی اضطراری احداث کرده‌اند تا همه‌ی روستاها به همدیگر متصل شوند. با توجه به اینکه اکثر جاده‌ها خراب شده بود و آن‌ها می‌خواستند این کار را در کم‌ترین زمان انجام دهند، هم‌اکنون گرافی که روستاها و جاده‌های اضطراری تشکیل می‌دهند، یک درخت فراگیر است.

بعد از احداث جاده‌های اضطراری، گروه آمار و تحقیقات تعداد اقلام اولیه‌ی مورد نیاز و تعداد اقلام موجود در هر روستا را حساب کرده است. حال مرکز مدیریت بحران خیکولند باید برای انتقال بارها دستورات لازم را صادر کند. هر دستور به این شکل است که «‎$C$‎ واحد از کمک‌ها از روستای ‎$u$‎ به روستای ‎$v$‎ انتقال پیدا کند». توجه کنید که پیش از انجام هر دستور، باید در روستای ‎$u$‎ حداقل ‎$C$‎ واحد از کمک‌های مردمی وجود داشته باشد و همچنین از روستای ‎$u$‎ به روستای ‎$v$‎ جاده‌ی اضطراری وجود داشته باشد.

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

بعد از انتشار اولیه‌ی این خبر، رئیس مرکز مدیریت بحران خیکولند با خبرگزاری خیکولناک تماس گرفت و اعلام کرد که در برنامه‌ی خیکوله اگرچه اولویت اول کمینه کردن تعداد دستورات است اما با توجه به نزدیک بودن فصل سرما، اینکه کل فرآیند انتقال بار در کمترین تعداد روز ممکن انجام شود نیز مهم است. وی در ادامه‌ی توضیحات خود گفت:

‎«‎برنامه‌ی خیکوله به این شکل عمل می‌کند که به عنوان ورودی میزان کمک‌های دریافتی و میزان کمک‌های مورد نیاز در هر روستا و همچنین نقشه‌ی گراف روستاها را می‌گیرد و در خروجی به ما می‌گوید که در هر روز چه دستوراتی را اجرا کنیم. با توجه به تخریب زیرساخت‌های مخابراتی اولویت اول برنامه‌‌ی خیکوله کمینه کردن تعداد دستورات است. سپس برنامه‌ی وی سعی دارد تعداد کل روزها را کمینه کند. دستورات در هر روز به گونه‌ای هستند که همزمان از صبح تا شب اجرا می‌شوند و بنابراین باید پیش‌نیاز اجرای همه‌ی آن‌ها از ابتدای روز در روستاها وجود داشته باشد‎.»‎

• در خط اول ‎$n$‎ تعداد روستاها آمده است.‎
• در خط دوم ‎$n$‎ عدد آمده است که عدد ‎$i$‎ام نشان‌گر تعداد واحدهای موجود از کمک‌های دریافتی در روستای ‎$i$‎ام است.‎
• در خط سوم ‎$n$‎ عدد آمده است که عدد ‎$i$‎ام نشان‌گر تعداد واحدهای مورد نیاز برای روستای ‎$i$‎ام است.
• در ‎$n-1$‎ خط بعدی، در هر خط دو عدد آمده است که شماره‌ی روستاهای دو سر یک جاده را نشان می‌دهند.
• در ۳۵ درصد تست‌ها: $n \leq 5000$‎
• در تمامی تست‌ها: $ 1\leq n \leq 10^5 $‎
• ‎تعداد واحدهای کمک‌رسانی در هر شهر بیش از ‎$10^7$‎ نیست، و مجموع تمام کمک‌رسانی‌ها در ‎int‎ می‌گنجد.

• در خط اول دو عدد ‎$k$‎ و ‎$d$‎ که به ترتیب تعداد دستورات لازم و تعداد روزهای لازم هستند را بنویسید.‎
• سپس در ‎$d$‎ خط بعدی در خط ‎$i$‎ام مجموعه دستوراتی که باید در روز ‎$i$‎ام اجرا شوند را بنویسد. به این شکل که در ابتدای خط یک عدد مثل ‎$t$‎ که نمایان‌گر تعداد دستورات است را بنویسید. سپس ‎$t$‎ دستوری که قرار است در آن روز اجرا شوند را به شکل ‎u v C‎ بنویسید.

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

• سوال قبل