سال گذشته در روز کریسمس، کیومرث یک درخت ریشهدار راسی با شمارههای تا خرید که ریشهی آن راس شماره و پدر راس شماره ام، راس با شماره است. در ابتدا درخت کیومرث به شکل یک مسیر است که درجه راس در آن یک است و روی هر راس تعدادی نامنفی گوی قرار دارد.
کیومرث که از شکل درخت خود ناراضی بود، تصمیم گرفت عملیات زیر را به تعدادی دلخواه روی درختش اعمال کند:
حال پس از گذشت یکسال، کیومرث درختی در خانهاش پیدا کرده که پدر راسهایش و تعداد گویهایشان میباشد. اما میخواهد بداند که آیا این درخت همان درخت کریسمس است یا خیر. جواب سوال او تنها در صورتی مثبت است که بتوان با شروع از درختی به شکل مسیر و اعمال تعدادی عملیات بر روی آن، به همین درخت برسیم. همچنین در صورت مثبت بودن جواب، مسیری را میخواهد پیدا کند که اگر راسهای آن را بهترتیب از ریشه تا آخر بنویسیم، لکسیکوگرافیکالی کمینه باشد.
در این سوال شما باید در سناریو مختلف، به کیومرث کمک کنید. در هر سناریو باید اعداد و و و را ورودی بگیرید، سپس تعیین کنید که آیا مسیر اولیهای وجود دارد یا نه، و در نهایت اگر بود، مسیر مورد نظر را هم خروجی دهید.
در خط اول ورودی تعداد سناریو ها میآید.
در هر سناریو در خط اول، دو عدد و به ترتیب و با فاصله از هم آمدهاند.
در هر یک از خط بعدی، دو عدد طبیعی و بهترتیب میآیند.
به ازای هر سناریو اگر مسیری وجود داشت، عبارت Yes
و در غیر این صورت، عبارت No
را چاپ کنید. سپس اگر بود، راسهای مسیر را به ترتیب و با فاصله از هم چاپ کنید. خروجی شما باید جایگشتی از اعداد تا باشد و خود ریشه را شامل نمیشود. دقت کنید که اگر بود، شما نباید هیچ خروجی دیگری بدهید!
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۱۲ | و به ازای تمامی ها برقرار است. |
۲ | ۱۵ | و به ازای تمامی ها برقرار است. |
۳ | ۴۱ | |
۴ | ۳۲ |
ا Scarecrow به گاتهام آمده و مردم شهر را مسموم کرده است. Batman با کمک دستیارانش توانسته پادزهری بسازد که مردم را شفا بدهد و حالا میخواهد آن را بین مردم پخش کند. نقشه شهر گاتهام به صورت یک درخت راسی میباشد که هر راس از آن یک منطقه را نشان میدهد. بتمن یک منطقه مانند را انتخاب میکند و پادزهر را از آن منطقه منتشر میکند. بتمن با افسر گوردن هماهنگ کرده است تا دقیقا یکی از جادهها (یال) را غیر قابل عبور کند تا اهالی منطقه نتوانند از فاصله این منطقه دورتر بروند زیرا اگر بتوانند خود را به منطقهای برسانند که فاصله آن با حداقل جاده باشد، پادزهر روی آنها اثر نمیکند.
به همین خاطر افسر گوردن از بتمن میخواهد تا تعداد جادههایی که با بسته شدن آنها پادزهر اثر نمیکند را به او بگوید. بتمن که هنوز راس اولیه و مقدار را انتخاب نکرده است، از شما کمک میخواهد تا این تعداد را به ازای سناریو مختلف جواب دهید.
در خط اول دو عدد طبیعی تعداد مناطق گاتهام و تعداد سناریوها بهترتیب میآیند.
در خط بعدی دنباله میآیند. به ازای هر جادهای میان دو منطقه و وجود دارد.
در هر یک از خط بعدی، دو عدد طبیعی و میآیند.
در خط جواب مربوط به هر سناریو را چاپ کنید.
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۸ | به ازای تمامی برقرار است. |
۲ | ۱۳ | و |
۳ | ۲۲ | |
۴ | ۱۸ | و فاصله منطقه با دورترین منطقه از آن حداکثر جاده میباشد. |
۵ | ۲۸ | |
۶ | ۱۱ | بدون محدودیت اضافی |
گراف ورودی دوم به شکل زیر است.
![]() |
---|
شکل ۱: شکل گراف نمونه ورودی ۲ |
اگر افسر گوردن هر جادهای به جز جادههای بین یا را ببندد، مردم میتوانند از منطقه به حداقل یکی از مناطق یا بروند و پادزهر روی آنها اثر نگذارد.
علیجان گاوصندوق هوشمندی دارد که رمز آن را فراموش کرده است. او میداند رمز گاوصندوقش جایگشتی از اعداد تا میباشد. علیجان از گاوصندوق هوشمند راهنمایی میگیرد تا رمز را پیدا کند. اگر رمز گاوصندوق جایگشت باشد، ابتدا عملیات زیر را انجام میدهد، و سپس جایگشت نهایی را به علیجان میدهد.
علیجان مقدار و جایگشت بعد از اجرا شدن کد بالا روی آن را دارد. او میخواهد بداند چند دنباله مختلف ممکن است رمز گاوصندوقش باشد.
در خط اول ورودی دو عدد طبیعی و سپس بهترتیب میآیند.
در خط دوم ورودی عدد بهترتیب میآیند.
در تنها خط خروجی، تعداد دنبالههای مختلفی که میتوانند رمز گاوصندوق باشند را چاپ کنید. از آنجایی که این مقدار ممکن است بزرگ باشد، باقیمانده تقسیم آن بر را چاپ کنید.
زیرمسئله | نمره | محدودیت |
---|---|---|
۱ | ۱۰ | |
۲ | ۲۱ | |
۳ | ۲۹ | و |
۴ | ۱۷ | |
۵ | ۲۳ | بدون محدودیت اضافی |
جایگشت یکی از جایگشتهایی است که ممکن است رمز گاوصندوق دوم باشد. عملیاتهایی که روی این جایگشت انجام میشود: