+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پروفسور موریارتی از شرارت خسته شده است و قصد دارد تا مدتی استراحت کند. او که نمی‌خواهد شرلوک هولمز مزاحم استراحت او شود، قصد دارد تا امنیت خانه اش را ارتقا دهد که شرلوک نتواند به آن نفوذ کند. در راستای افزایش امنیت خانه، قصد دارد ضلع شمالی خانه را با آجرهایی مخصوص دیوارکشی کند. پس از تماس با کارخانه متوجه می‌شود که کارخانه فقط آجرهایی با طول $b$ تولید می‌کند و امکان تولید آجر با طول دیگری وجود ندارد. او متوجه شد که ممکن است این آجرها نتوانند کل ضلع خانه را پوشش دهند، حال برای او سوال پیش آمده است که اگر طول ضلع شمالی خانه $a$ باشد، حداقل چه مقدار از ضلع خانه پوشیده نشده باقی خواهد ماند. دقت کنید که امکان چیدن آجرها کنار هم وجود دارد، ولی به دلیل نوع طراحی خاصی که آجرها دارند، امکان شکاندن آجرها به قطعات کوچکتر وجود ندارد. همچنین امکان اینکه طولی بیشتر از طول ضلع شمالی خانه دیوارکشی شود نیز وجود ندارد. پروفسور که نمی‌خواهد تعطیلات خود را صرف انجام محاسبات کند، از شما خواسته تا بگویید حداقل چه طولی از ضلع خانه، پوشیده نشده باقی خواهد ماند. # ورودی در تنها خط ورودی دو عدد $a$ و $b$ به شما داده می‌شود که با یک فاصله از یکدیگر جدا شده‌اند. $a$ بیانگر طول ضلع شمالی خانه و $b$ برابر طول یک آجر است. $$1 \leq a, b \leq 10^{18}$$ # خروجی در تنها خط خروجی باید مقدار حداقل طولی که نمی‌توان با آجر پوشاند را نمایش دهید. # مثال‌ها ## ورودی نمونه ۱ ``` 5 2 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 10 8 ``` ## خروجی نمونه ۲ ``` 2 ```

دیوارکشی

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

پروفسور موریارتی از شرارت خسته شده است و قصد دارد تا مدتی استراحت کند. او که نمی‌خواهد شرلوک هولمز مزاحم استراحت او شود، قصد دارد تا امنیت خانه اش را ارتقا دهد که شرلوک نتواند به آن نفوذ کند. در راستای افزایش امنیت خانه، قصد دارد ضلع شمالی خانه را با آجرهایی مخصوص دیوارکشی کند. پس از تماس با کارخانه متوجه می‌شود که کارخانه فقط آجرهایی با طول $b$ تولید می‌کند و امکان تولید آجر با طول دیگری وجود ندارد. او متوجه شد که ممکن است این آجرها نتوانند کل ضلع خانه را پوشش دهند، حال برای او سوال پیش آمده است که اگر طول ضلع شمالی خانه $a$ باشد، حداقل چه مقدار از ضلع خانه پوشیده نشده باقی خواهد ماند. دقت کنید که امکان چیدن آجرها کنار هم وجود دارد، ولی به دلیل نوع طراحی خاصی که آجرها دارند، امکان شکاندن آجرها به قطعات کوچکتر وجود ندارد. همچنین امکان اینکه طولی بیشتر از طول ضلع شمالی خانه دیوارکشی شود نیز وجود ندارد. پروفسور که نمی‌خواهد تعطیلات خود را صرف انجام محاسبات کند، از شما خواسته تا بگویید حداقل چه طولی از ضلع خانه، پوشیده نشده باقی خواهد ماند.

ورودی🔗

در تنها خط ورودی دو عدد $a$ و $b$ به شما داده می‌شود که با یک فاصله از یکدیگر جدا شده‌اند. $a$ بیانگر طول ضلع شمالی خانه و $b$ برابر طول یک آجر است.

$1 \leq a, b \leq 10^{18}$

خروجی🔗

در تنها خط خروجی باید مقدار حداقل طولی که نمی‌توان با آجر پوشاند را نمایش دهید.

مثال‌ها🔗

ورودی نمونه ۱🔗

5 2

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

10 8

خروجی نمونه ۲🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- خان‌های برره همواره سعی می‌کردند تا مردم را از تکنولوژی دور نگهدارند. اما به علت نارضایتی‌های عمومی بالاخره تصمیم به احداث یک سینما در برره‌ی علیا گرفتند. با توجه به اختلافات ریشه‌ای بالا برره و پایین برره، تصمیم گرفته شده که اکران فیلم به صورت مجزا برای هر دو گروه انجام شود. همواره جمعیت پایین برره و بالا برره یکی بوده اما پس از جنگ اخیر برره‌ای‌ها، جمعیت بالا برره $a$ و جمعیت پایین برره $b$ نفر است و همه‌ی اهالی متقاضی دیدن فیلم در سینما هستند. با توجه به نسبت فامیلی شیرفرهاد با اهالی برره‌ی بالا و پایین، پروژه‌ی احداث سینما به وی سپرده شده است. از آنجا که شیرفرهاد شایستگی لازم را برای این کار ندارد، وجدان بیدارش از او می‌خواهد کیانوش، داماد خانواده را به این کار بگمارد. ظرفیت سالن سینما هنوز مشخص نشده است، ولی می‌خواهیم آن را برابر عددی مثل $c$ قرار دهیم. شورای عالی نظمیه‌ی برره برای سنگ اندازی در فرآیند حرکت به سوی مدرنیته‌ی کیانوش سیاست‌هایی را برای ظرفیت سالن ابلاغ کرده است. در هر سانس حداکثر به اندازه‌ی ظرفیت سالن ($c$ نفر) می‌توانند داخل سالن باشند. همچنین تعداد کل سانس‌ها کم‌ترین مقدار ممکن باشد. همچنین به ازای هر گروه حداقل یک سانس باید به طور کامل پر شود. پیش بینی‌ها حاکی از آن است که اهالی همگی به سمت سالن آمده و سنت صف ایستادن را زنده نگه خواهد داشت. از طرف دیگر، با توجه به جنگ اخیر، دسته‌ی بزرگتر از بیم هشتبلکوی دسته‌ی اقلیت حاضر نیست هنگام ایستادن در صف جمعیت کمتری نسبت به دسته ی کوچکتر داشته باشد. # ورودی در خط اول ورودی دو عدد $a$ و $b$ که به ترتیب نشان دهنده‌ی جمعیت برره‌ی علیا (بالا برره) و برره‌ی سفلی (پایین برره) است داده شده است. $$1 \leq a, b \leq 10^{18}$$ # خروجی در تنها خط خروجی مقدار عدد $c$ که برابر با ظرفیت سالن سینما با شرایط مذکور است را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 6 12 ``` ## خروجی نمونه ۱ ``` 6 ``` ## ورودی نمونه ۲ ``` 12 8 ``` ## خروجی نمونه ۲ ``` 8 ``` ## ورودی نمونه ۳ ``` 15 15 ``` ## خروجی نمونه ۳ ``` 15 ```

سینما برره

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

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

همواره جمعیت پایین برره و بالا برره یکی بوده اما پس از جنگ اخیر برره‌ای‌ها، جمعیت بالا برره $a$ و جمعیت پایین برره $b$ نفر است و همه‌ی اهالی متقاضی دیدن فیلم در سینما هستند. با توجه به نسبت فامیلی شیرفرهاد با اهالی برره‌ی بالا و پایین، پروژه‌ی احداث سینما به وی سپرده شده است. از آنجا که شیرفرهاد شایستگی لازم را برای این کار ندارد، وجدان بیدارش از او می‌خواهد کیانوش، داماد خانواده را به این کار بگمارد.

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

ورودی🔗

در خط اول ورودی دو عدد $a$ و $b$ که به ترتیب نشان دهنده‌ی جمعیت برره‌ی علیا (بالا برره) و برره‌ی سفلی (پایین برره) است داده شده است.

$1 \leq a, b \leq 10^{18}$

خروجی🔗

در تنها خط خروجی مقدار عدد $c$ که برابر با ظرفیت سالن سینما با شرایط مذکور است را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

6 12

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

12 8

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

15 15

خروجی نمونه ۳🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دانشکده‌ی مهندسی کامپیوتر قصد دارد به مناسب برگزاری مسابقه‌ی ICPC دانشکده را تزئین کند. برای این کار دو ریسه لامپ تهیه شده است که برروی هر کدام از آن‌ها $n$ لامپ قرار دارد. پس از انجام تزئینات از دبیر مسابقه دعوت می‌شود تا از محیط مسابقه بازدید کند و نظر خود را در این باره بگوید. دبیر مسابقات هنگام بازدید، متوجه می‌شود که دو ریسه از نظر روشن و خاموش بودن لامپ ها با جایگاه یکسان، مانند هم نیستند. او که بسیار به تقارن اهمیت می‌دهد، از مسئول تزئینات درخواست می‌کند که هر دو ریسه را از نظر روشن یا خاموش بودن لامپ ها یکسان کند. مسئول تزئینات هنگام انجام این کار، متوجه می‌شود که به دلیل بروز مشکل فنی، نمی‌تواند یک لامپ را به تنهایی تغییر حالت دهد و باید در هر گام، دقیقاً دو لامپ را به شکل همزمان تغییر حالت دهد، البته لزومی ندارد که هر دو لامپ متعلق به یک ریسه باشند، ولی باید در هر گام دو لامپ به شکل همزمان تغییر وضعیت دهند. او که به شدت درگیر رسیدگی به سایر مسائل است، از شما درخواست کرده در این امر به او کمک کنید. # ورودی در خط اول ورودی عدد $n$ که بیانگر تعداد لامپ‌های هر ریسه است به شما داده می‌شود. در هر یک از خطوط دوم و سوم یک رشته باینری به طول $n$ داده می‌شود که بیانگر وضعیت لامپ‌ها در هر یک از ریسه‌هاست. `0` به معنی خاموش بودن لامپ و `1` به معنای روشن بودن آن است. $$1 \leq n \leq 10^6$$ # خروجی در صورتی که امکان یکسان کردن ریسه‌ها با شرایط گفته شده در صورت سوال وجود دارد، در خروجی حداقل تعداد گام لازم برای یکسان کردن ریسه‌ها را چاپ کنید و در غیر این صورت، باید در خروجی عبارت `NO` چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 5 00011 11011 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 7 0101010 1101100 ``` ## خروجی نمونه ۲ ``` NO ```

نورانی

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

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

ورودی🔗

در خط اول ورودی عدد $n$ که بیانگر تعداد لامپ‌های هر ریسه است به شما داده می‌شود. در هر یک از خطوط دوم و سوم یک رشته باینری به طول $n$ داده می‌شود که بیانگر وضعیت لامپ‌ها در هر یک از ریسه‌هاست. 0 به معنی خاموش بودن لامپ و 1 به معنای روشن بودن آن است.

$1 \leq n \leq 10^6$

خروجی🔗

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

مثال‌ها🔗

ورودی نمونه ۱🔗

5
00011
11011

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

7
0101010
1101100

خروجی نمونه ۲🔗

NO

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کیان داخل یک اتاق گیر افتاده است و جایی را نمی‌بیند. می‌دانیم کف این اتاق مربع شکل با $n \times n$ کاشی مربع شکل کاشی کاری شده است. همچنین هر کاشی شماره‌ای یکتا دارد و شماره گذاری کاشی ها به شکل مارپیچ است. برای مثال شکل زیر شماره گذاری کاشی‌ها برای $n = 5$ را نشان می‌دهد. \[ \begin{array}{ccccc} 13 & 12 & 11 & 10 & 9 \\ 14 & 23 & 22 & 21 & 8 \\ 15 & 24 & 25 & 20 & 7 \\ 16 & 17 & 18 & 19 & 6 \\ 1 & 2 & 3 & 4 & 5 \\ \end{array} \] کیان می‌داند یک شمع داخل این اتاق وجود دارد و می‌خواهد به آن برسد اما چون اتاق تاریک است جایی را نمی‌بیند. او از شما می‌خواهد که با گرفتن شماره کاشی‌ای که کیان روی آن ایستاده است و کاشی‌ای که شمع روی آن قرار دارد، او را راهنمایی کنید که چقدر باید در هر جهت حرکت کند تا به شمع برسد. # ورودی در تنها خط ورودی به ترتیب سه عدد $n$ و $s$ و $d$ با فاصله می‌آیند که طول اتاق، شماره‌ی کاشی کیان و شماره کاشی‌ای که شمع روی آن قرار دارد هستند. $$1 \leq n \leq 2000$$ $$1 \leq s \neq d \leq n^2$$ # خروجی در اولین خط خروجی، یک عدد و یک کاراکتر با فاصله می‌آیند. عددی که چاپ می‌شود مقداری است که کیان باید در جهت افقی جابجا شود و اگر باید به سمت چپ برود کاراکتر برابر `L` و اگر باید به راست برود کاراکتر برابر `R` خواهد بود. اگر کیان نباید در جهت افقی جابجا شود، از این خط صرف نظر می‌شود. در دومین خط خروجی، یک عدد و یک کاراکتر با فاصله می‌آیند. عددی که چاپ می‌شود مقداری است که کیان باید در جهت عمودی جابجا شود و اگر باید به سمت بالا برود کاراکتر برابر `U` و اگر باید به پایین برود کاراکتر برابر `D` خواهد بود. اگر کیان نباید در جهت عمودی جابجا شود، از این خط صرف نظر می‌شود. # مثال‌ها ## ورودی نمونه ۱ ``` 5 1 25 ``` ## خروجی نمونه ۱ ``` 2 R 2 U ``` ## ورودی نمونه ۲ ``` 5 3 22 ``` ## خروجی نمونه ۲ ``` 3 U ``` ## ورودی نمونه ۳ ``` 15 67 24 ``` ## خروجی نمونه ۳ ``` 3 R 8 U ```

مربع مارپیچ

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

کیان داخل یک اتاق گیر افتاده است و جایی را نمی‌بیند. می‌دانیم کف این اتاق مربع شکل با $n \times n$ کاشی مربع شکل کاشی کاری شده است. همچنین هر کاشی شماره‌ای یکتا دارد و شماره گذاری کاشی ها به شکل مارپیچ است. برای مثال شکل زیر شماره گذاری کاشی‌ها برای $n = 5$ را نشان می‌دهد.

$\begin{array}{ccccc} 13 & 12 & 11 & 10 & 9 \\ 14 & 23 & 22 & 21 & 8 \\ 15 & 24 & 25 & 20 & 7 \\ 16 & 17 & 18 & 19 & 6 \\ 1 & 2 & 3 & 4 & 5 \\ \end{array}$

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

ورودی🔗

در تنها خط ورودی به ترتیب سه عدد $n$ و $s$ و $d$ با فاصله می‌آیند که طول اتاق، شماره‌ی کاشی کیان و شماره کاشی‌ای که شمع روی آن قرار دارد هستند.

$1 \leq n \leq 2000$ $1 \leq s \neq d \leq n^2$

خروجی🔗

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

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

مثال‌ها🔗

ورودی نمونه ۱🔗

5 1 25

خروجی نمونه ۱🔗

2 R
2 U

ورودی نمونه ۲🔗

5 3 22

خروجی نمونه ۲🔗

3 U

ورودی نمونه ۳🔗

15 67 24

خروجی نمونه ۳🔗

3 R
8 U

خوشحالی پرانتزی

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

دانشجویی یک رشته از پرانتزها پیدا کرده است. او می‌داند یک پرانتزگذاری درست به شکل زیر است:

$()$ یک پرانتزگذاری صحیح است.
اگر $S$ یک پرانتزگذاری صحیح باشد، $(S)$ هم یک پرانتزگذاری درست است.
اگر $S$ و $T$ یک پرانتزگذاری درست باشد، $TS$ که از کنار هم گذاشتن آن دو رشته به دست می‌آید نیز پرانتزگذاری صحیح است.

همچنین یک شیفت دوری به اندازه‌ی $k$ روی رشته‌ی $S$ باعث تبدیل شدن آن به رشته‌ی $T$ می‌شود که داریم: $\forall \,0 \leq i \lt |S|, \quad T[i] = S[(i + k) mod |S|]$

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

ورودی🔗

در خط اول ورودی عدد $n$ که طول رشته است آمده است. در خط دوم ورودی رشته‌ی $S$ شامل کاراکتر های ) و ( است می‌آید.

خروجی🔗

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

مثال‌ها🔗

ورودی نمونه ۱🔗

6
))()((

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

6
())(((

خروجی نمونه ۲🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در جزیره‌ی فلوکی $k$ قبیله‌ی مختلف قرار دارند که در $k$ محل مختلف زندگی می‌کنند. نقشه‌ی جزیره‌ی فلوکی به شکل یک گراف همبند است که دارای $n$ محل (راس) و $n-1$ جاده (یال) است. به دلیل اختلافات عقیده ای که در این مدت بین قبایل این جزیره رخ داده است، روند جنگ های داخلی آن‌ها شروع شده است؛ در هر روز هریک از قبایل به تمام محل های مجاور جاده ای خود نفوذ می‌کند و آن محل را به تصرف خود در می‌آورد. در صورتی که دو قبیله به یک محل مشترک برسند و یا یکی از قبایل به محلی برسد که از قبل توسط قبیله ای دیگر تصرف شده باشد، این دو قبیله با یک دیگر به مذاکره می‌پردازند و در نتیجه باهم متحد می‌شوند و از این پس مانند یک قبیله‌ی واحد عمل می‌کنند (ممکن است در یک لحظه حتی بیش از دو قبیله باهم متحد شوند!). شما به عنوان جاسوس سازمان صلح جهانی وظیفه دارید به کمک گراف جزیره ی فلوکی که در ورودی به شما داده می‌شود، اولین روزی از جنگ که تمام این $k$ قبیله طی جنگ داخلی خود با یک دیگر متحد می‌شوند را پیدا کنید. # ورودی در خط اول ورودی عدد $n$ و $k$ که به ترتیب برابر تعداد محل‌ها و قبیله های جزیره هستند داده می‌شود. $$1 \leq n \leq 10^6$$ در هرکدام از $n-1$ خط بعدی دو عدد $u_i$ و $v_i$ آمده است که نشان دهنده‌ی دو سر یال $i$ ام گراف جزیره است. سپس $k$ عدد مختلف در یک سطر داده می‌شود که عدد $a_i$ راس ابتدایی قبیله‌ی $i$ در گراف ورودی است. تضمین می‌شود گراف ورودی شرایط لازم را دارد و معتبر است. $$1 \leq k, a_i \leq n$$ # خروجی در تنها خط خروجی کم‌ترین تعداد روزهایی که برای اتحاد و توافق تمام قبیله‌ها باید سپری شود را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 5 3 1 2 1 3 1 4 1 5 2 3 4 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 4 2 1 2 2 3 3 4 1 4 ``` ## خروجی نمونه ۲ ``` 2 ``` ## ورودی نمونه ۳ ``` 8 3 1 2 2 3 3 4 4 5 5 6 3 7 7 8 2 6 8 ``` ## خروجی نمونه ۳ ``` 2 ```

هاکونا ماتاتا

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

در جزیره‌ی فلوکی $k$ قبیله‌ی مختلف قرار دارند که در $k$ محل مختلف زندگی می‌کنند. نقشه‌ی جزیره‌ی فلوکی به شکل یک گراف همبند است که دارای $n$ محل (راس) و $n-1$ جاده (یال) است.

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

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

ورودی🔗

در خط اول ورودی عدد $n$ و $k$ که به ترتیب برابر تعداد محل‌ها و قبیله های جزیره هستند داده می‌شود.

$1 \leq n \leq 10^6$

در هرکدام از $n-1$ خط بعدی دو عدد $u_i$ و $v_i$ آمده است که نشان دهنده‌ی دو سر یال $i$ ام گراف جزیره است. سپس $k$ عدد مختلف در یک سطر داده می‌شود که عدد $a_i$ راس ابتدایی قبیله‌ی $i$ در گراف ورودی است. تضمین می‌شود گراف ورودی شرایط لازم را دارد و معتبر است.

$1 \leq k, a_i \leq n$

خروجی🔗

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

مثال‌ها🔗

ورودی نمونه ۱🔗

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

خروجی نمونه ۲🔗

ورودی نمونه ۳🔗

خروجی نمونه ۳🔗

بازی آرایه‌ای

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

فراز در یک بازی شرکت کرده است اما چندان حوصله این بازی را ندارد. شرح بازی به این شکل است که فراز با دو دنباله $a_1, a_2, \dots, a_n\,$ و $b_1, b_2, \dots, b_n\,$ مواجه است به شکلی که تمامی $a_i$ ها مثبت و تمامی $b_i$ ها در ابتدا صفر هستند. فراز در هر مرحله از بازی یک $i$ دلخواه انتخاب می‌کند به شکلی که $1 \leq i \leq n$ و سپس به اندازه $a_i$ ، به $b_i$ اضافه یا کم می‌کند. یعنی قرار می‌دهد $b_i \leftarrow b_i - a_i \,$ یا $b_i \leftarrow b_i + a_i \,$ .

هدف بازی این است که پس از تعدادی مرحله، دنباله $b$ اکیداً صعودی شود. یعنی داشته باشیم $b_1 \lt b_2 \lt \dots \lt b_n$ .

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

ورودی🔗

خط اول شامل عدد $n$ است که نشان دهنده طول دو دنباله $a$ و $b$ خواهد بود. $1 \leq n \leq 5000$

خط دوم شامل $n$ عدد است که به ترتیب نشان دهنده دنباله $a_1, a_2, \dots, a_n \,$ هستند. $1 \leq a_i \leq 10^9$

خروجی🔗

در تنها خط خروجی حداقل مراحل لازم بازی فراز را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

5
1 2 3 4 5

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

7
1 2 1 2 1 2 1

خروجی نمونه ۲🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بهرام و محسن که تصمیم گرفته بودند با کمک یکدیگر تدریس کلاس طراحی الگوریتم ها را بر عهده بگیرند به تازگی با یک مشکل اساسی مواجه شده‌اند و قرار است راهشان را از هم جدا کنند. ریشه‌ی مشکل نگرش نابخردانه‌ی محسن در تشخیص استعداد یک دانشجو در طراحی الگوریتم است. بهرام بدرستی معتقد است که استعداد طراحی الگوریتم دانشجویان با میزان استعداد آن‌ها در ریاضیات گسسته رابطه‌ی مستقیم دارد. اما محسن می‌گوید دانشجویی که ریاضیات پیوسته را بهتر بفهمد طراح الگوریتم بهتری خواهد شد. بدین ترتیب قرار بر آن شد که دانشجویان کلاس را به دو گروه تقسیم کرده و هر کدام تدریس گروهی را به عهده بگیرند. تقسیم اعضای کلاس بدین صورت است که هر کس در نوبت خود یک دانشجو را انتخاب می‌کند سپس نوبت انتخاب را به دیگری واگذار می‌کند. این رویه تا انتخاب شدن تمام دانشجویان ادامه دارد. از آنجایی که بهرام اخلاقی پهلوانی دارد و روی خامی محسن حساب ویژه‌ای باز کرده است اجازه می‌دهد اولین انتخاب بر عهده‌ی محسن باشد. محسن نابخرد از استراتژی خبیصانه استفاده می‌کند. به این صورت که هر بار از بین دانشجویان باقیمانده فردی که بیشترین استعداد ریاضیات پیوسته را دارد انتخاب می‌کند. اگر چندین دانشجو با این شرایط وجود داشته باشد، محسن یکی از آن‌ها را به دلخواه خودش انتخاب می‌کند. بهرام به دلیل شناخت عمیقی که از محسن دارد خبیصانه بودن او را حدس زده و می‌خواهد بداند بیشترین مقدار ممکن برای مجموع استعداد ریاضیات گسسته دانشجویان انتخابی خودش، مستقل از حرکات محسن، چند است. با محاسبه‌ی این مقدار به کمک بهرام بشتابید. # ورودی در خط اول ورودی عدد $n$ که بیانگر تعداد دانشجویان است به شما داده می‌شود. $$1 \leq n \leq 100 \, 000$$ در هر یک از خطوط دوم و سوم به ترتیب $n$ عدد صحیح $a_1, a_2, \dots, a_n\,$ و $b_1, b_2, \dots, b_n\,$ داده می‌شود که $a_i$ بیانگر استعداد دانشجوی $i$ در ریاضیات پیوسته و $b_i$ بیانگر میزان استعداد دانشجوی $i$ در ریاضیات گسسته است. $$1 \leq a_i, b_i \leq 10^9$$ # خروجی در خروجی بیشترین مقدار ممکن برای مجموع استعداد ریاضیات گسسته دانشجویان انتخابی توسط بهرام را با فرض خبیصانه بودن استراتژی محسن چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 3 1 8 4 12 11 1 ``` ## خروجی نمونه ۱ ``` 12 ``` ## ورودی نمونه ۲ ``` 5 1 2 3 4 5 2 3 4 5 6 ``` ## خروجی نمونه ۲ ``` 8 ```

کلاس طراحی الگوریتم

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

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

ورودی🔗

در خط اول ورودی عدد $n$ که بیانگر تعداد دانشجویان است به شما داده می‌شود. $1 \leq n \leq 100 \, 000$

در هر یک از خطوط دوم و سوم به ترتیب $n$ عدد صحیح $a_1, a_2, \dots, a_n\,$ و $b_1, b_2, \dots, b_n\,$ داده می‌شود که $a_i$ بیانگر استعداد دانشجوی $i$ در ریاضیات پیوسته و $b_i$ بیانگر میزان استعداد دانشجوی $i$ در ریاضیات گسسته است.

$1 \leq a_i, b_i \leq 10^9$

خروجی🔗

در خروجی بیشترین مقدار ممکن برای مجموع استعداد ریاضیات گسسته دانشجویان انتخابی توسط بهرام را با فرض خبیصانه بودن استراتژی محسن چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

3
1 8 4
12 11 1

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

5
1 2 3 4 5
2 3 4 5 6

خروجی نمونه ۲🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- محسن به تازگی به دلیل مشکلات مالی تغییر شغل داده و راننده تاکسی شده است. او در شهر آمل زندگی می‌کند. این شهر به صورت یک گراف بدون جهت $n$ راسی و $m$ یالی است که خانه‌ی محسن در راس $h$ واقع شده است. هر کدام از یال‌های این گراف دارای وزن است که نشان دهنده مدت زمانی (واحد ثانیه) است که طول می‌کشد محسن با ماشین خودش از آن‌ها رد شود. با توجه به وضعیت مالی بد، محسن نزد بهرام رفته تا در خصوص اینکه چگونه از این شغل درآمد بیشتری کسب کند نیز از رهنمودهای بهرام استفاده کند. بهرام به محسن می‌گوید که او از همه درخواست‌های مردم برای دربستی در روز آینده خبر دارد و به او می‌گوید با دانستن آن‌ها محسن می‌تواند بیشترین درآمد را داشته باشد. به طور مشخص بهرام به او می‌گوید در روز آینده $k$ درخواست وجود دارد که $i$امین درخواست در زمان $t_i$ و در راس $s_i$ داده می‌شود و مقصد آن $d_i$ است. همچنین محسن از این درخواست $val_i$ درآمد خواهد داشت. محسن تنها زمانی می‌تواند یک درخواست را قبول کند که در زمان درخواست در $s_i$ حاضر باشد. هچنین او می‌تواند بین سفرهای خویش در یک راس دلخواه استراحت کند و از بین مسیرهای ممکن بین مبدا و مقصد می‌تواند هر مسیری را انتخاب کند. محسن صبح از ساعت `00:00:07` صبح از خانه بیرون می‌رود و شب تا ساعت `00:00:23` می‌خواهد به خانه برسد. پس از دریافت این اطلاعات از بهرام، محسن نمی‌داند چگونه این اطلاعات به او در کسب درآمد بیشتر کمک می‌کند ولی مطمئن است که رهنمودهای بهرام مثل همیشه به او کمک خواهد کرد. به همین دلیل او از شما در کسب بیشترین درآمد روزانه با توجه به اطلاعات بهرام درخواست کمک کرده است. # ورودی در سطر اول ورودی به ترتیب چهار عدد $n$ و $m$ و $k$ و $h$ آمده است که به ترتیب نماینگر تعداد رئوس گراف، تعداد یال هال گراف، تعداد درخواست‌ها و شماره راس خانه‌ی محسن است. $$1 \leq n \leq 500$$ $$1 \leq m \leq \frac{n(n - 1)}{2}$$ $$1 \leq k \leq 2000$$ در $m$ سطر بعدی مشخصات یال‌های گراف آمده است. در سطر $i$اُم به ترتیب $u$ و $v$ و $dis_i$ آمده است که نشان دهنده یال موجود بین $u$ و $v$ و طول آن یال است. در $k$ سطر انتهایی مشخصات درخواست‌ها آمده است. ابتدا $s_i$ و $d_i$ به عنوان نقاط شروع و پایان درخواست آمده اند. سپس مقدار $val_i$ آمده است که نشان دهنده پولی است که محسن از این درخواست به دست می‌آورد. در انتها زمان درخواست به فرمت `ss:mm:hh` آمده است که نشان دهنده زمانی است که درخواست داده می‌شود. $$1 \leq u, v, s_i, d_i, h \leq n$$ $$1 \leq dis_i, val_i \leq 100 \, 000$$ # خروجی در تنها سطر خروجی بیشترین میزان پولی که محسن می‌تواند به دست بیاورد را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 5 4 3 1 1 2 3600 2 3 3600 3 4 3600 4 5 3600 1 3 10 08:00:00 2 4 30 11:00:01 4 5 40 11:30:00 ``` ## خروجی نمونه ۱ ``` 50 ``` ## ورودی نمونه ۲ ``` 4 6 5 1 1 2 1800 2 3 1800 3 4 1800 4 1 1800 1 3 3800 2 4 3300 1 3 10 08:15:00 2 4 15 07:36:00 3 1 20 09:00:00 1 4 15 10:00:00 4 3 100 22:15:00 ``` ## خروجی نمونه ۲ ``` 35 ```

راننده تاکسی

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

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

بهرام به محسن می‌گوید که او از همه درخواست‌های مردم برای دربستی در روز آینده خبر دارد و به او می‌گوید با دانستن آن‌ها محسن می‌تواند بیشترین درآمد را داشته باشد. به طور مشخص بهرام به او می‌گوید در روز آینده $k$ درخواست وجود دارد که $i$ امین درخواست در زمان $t_i$ و در راس $s_i$ داده می‌شود و مقصد آن $d_i$ است. همچنین محسن از این درخواست $val_i$ درآمد خواهد داشت. محسن تنها زمانی می‌تواند یک درخواست را قبول کند که در زمان درخواست در $s_i$ حاضر باشد. هچنین او می‌تواند بین سفرهای خویش در یک راس دلخواه استراحت کند و از بین مسیرهای ممکن بین مبدا و مقصد می‌تواند هر مسیری را انتخاب کند. محسن صبح از ساعت 00:00:07 صبح از خانه بیرون می‌رود و شب تا ساعت 00:00:23 می‌خواهد به خانه برسد. پس از دریافت این اطلاعات از بهرام، محسن نمی‌داند چگونه این اطلاعات به او در کسب درآمد بیشتر کمک می‌کند ولی مطمئن است که رهنمودهای بهرام مثل همیشه به او کمک خواهد کرد. به همین دلیل او از شما در کسب بیشترین درآمد روزانه با توجه به اطلاعات بهرام درخواست کمک کرده است.

ورودی🔗

در سطر اول ورودی به ترتیب چهار عدد $n$ و $m$ و $k$ و $h$ آمده است که به ترتیب نماینگر تعداد رئوس گراف، تعداد یال هال گراف، تعداد درخواست‌ها و شماره راس خانه‌ی محسن است. $1 \leq n \leq 500$ $1 \leq m \leq \frac{n(n - 1)}{2}$ $1 \leq k \leq 2000$

در $m$ سطر بعدی مشخصات یال‌های گراف آمده است. در سطر $i$ اُم به ترتیب $u$ و $v$ و $dis_i$ آمده است که نشان دهنده یال موجود بین $u$ و $v$ و طول آن یال است.

در $k$ سطر انتهایی مشخصات درخواست‌ها آمده است. ابتدا $s_i$ و $d_i$ به عنوان نقاط شروع و پایان درخواست آمده اند. سپس مقدار $val_i$ آمده است که نشان دهنده پولی است که محسن از این درخواست به دست می‌آورد. در انتها زمان درخواست به فرمت ss:mm:hh آمده است که نشان دهنده زمانی است که درخواست داده می‌شود.

$1 \leq u, v, s_i, d_i, h \leq n$ $1 \leq dis_i, val_i \leq 100 \, 000$

خروجی🔗

در تنها سطر خروجی بیشترین میزان پولی که محسن می‌تواند به دست بیاورد را چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

5 4 3 1
1 2 3600
2 3 3600
3 4 3600
4 5 3600
1 3 10 08:00:00
2 4 30 11:00:01
4 5 40 11:30:00

خروجی نمونه ۱🔗

ورودی نمونه ۲🔗

4 6 5 1
1 2 1800
2 3 1800
3 4 1800
4 1 1800
1 3 3800
2 4 3300
1 3 10 08:15:00
2 4 15 07:36:00
3 1 20 09:00:00
1 4 15 10:00:00
4 3 100 22:15:00

خروجی نمونه ۲🔗

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- صادق و ماهان که تحت تاثیر داستان گرینچ قرار گرفته اند، و با توجه به حال و هوای عید، تصمیم گرفته‌اند درخت کریسمس امیر را به سرقت ببرند. آن ها سوار بر وانت، به تهران پارس رفتند و دزدکی وارد خانه امیر شدند. اما در لحظه خروج متوجه معمایی شدند که امیر با استفاده از آن، درختش را قفل کرده بود. ماهان که المپیادی بوده است، معما را به سرعت متوجه شد و برای صادق به این شکل شرح داد. درختی $n$ راسی داریم که روی هر یال آن، یک کاراکتر کوچک انگلیسی نوشته شده است. همچنین رشته رمز $s_1 s_2 \dots s_m\,$ را در اختیار داریم. می‌خواهیم مسیری از این درخت (بدون تکرار یال‌ها) بیابیم که با پیمودن آن و به هم چسباندن یال‌های طی شده، رشته رمز را تولید کنیم. در واقع می‌خواهیم بدانیم مسیری با یال‌های $e_{i_1}, e_{i_2}, \dots, e_{i_m}\,$ بیابیم که رشته $c_{i_1}, c_{i_2}, \dots, c_{i_m}\,$ برابر با $s_1, s_2, \dots, s_m\,$ باشد. که $c_{i_j}$ کاراکتر نوشته روی یال $e_{i_j}$ است. شما باید در این مسئله، این مسیر را بیابید یا اعلام کنید هیچ مسیری با ویژگی گفته شده وجود ندارد. # ورودی در خط اول ورودی عدد $n$ که بیانگر تعداد رئوس درخت است به شما داده می‌شود. در خط $i$ام از $n-1$ خط بعدی، به ترتیب $u_i$ و $v_i$ و $c_i$ داده می‌شوند که نشان دهنده یال بین رئوس $v_i$ و $u_i$ با حرف $c_i$ هستند. تضمین می‌شود $c_i$ یک حرف کوچک انگلیسی است. همچنین تضمین می‌شود یال‌های داده شده تشکیل یک درخت می‌دهند. در خط آخر، رشته $s$ که تنها از حروف کوچک انگلیسی تشکیل شده است، به شما داده می‌شود. # خروجی در تنها خط خروجی دو عدد جدا شده توسط یک فاصله چاپ کنید که به ترتیب نشان دهنده راس شروع مسیر و راس انتهای مسیر هستند. در صورتی که چنین مسیری وجود ندارد، `-1 -1` چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 4 1 2 a 2 3 b 3 4 c bc ``` ## خروجی نمونه ۱ ``` 2 4 ``` ## ورودی نمونه ۲ ``` 4 1 2 a 2 3 b 3 4 c ac ``` ## خروجی نمونه ۲ ``` -1 -1 ```

درختی یا بوته‌ای

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

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

درختی $n$ راسی داریم که روی هر یال آن، یک کاراکتر کوچک انگلیسی نوشته شده است. همچنین رشته رمز $s_1 s_2 \dots s_m\,$ را در اختیار داریم. می‌خواهیم مسیری از این درخت (بدون تکرار یال‌ها) بیابیم که با پیمودن آن و به هم چسباندن یال‌های طی شده، رشته رمز را تولید کنیم. در واقع می‌خواهیم بدانیم مسیری با یال‌های $e_{i_1}, e_{i_2}, \dots, e_{i_m}\,$ بیابیم که رشته $c_{i_1}, c_{i_2}, \dots, c_{i_m}\,$ برابر با $s_1, s_2, \dots, s_m\,$ باشد. که $c_{i_j}$ کاراکتر نوشته روی یال $e_{i_j}$ است.

شما باید در این مسئله، این مسیر را بیابید یا اعلام کنید هیچ مسیری با ویژگی گفته شده وجود ندارد.

ورودی🔗

در خط اول ورودی عدد $n$ که بیانگر تعداد رئوس درخت است به شما داده می‌شود. در خط $i$ ام از $n-1$ خط بعدی، به ترتیب $u_i$ و $v_i$ و $c_i$ داده می‌شوند که نشان دهنده یال بین رئوس $v_i$ و $u_i$ با حرف $c_i$ هستند. تضمین می‌شود $c_i$ یک حرف کوچک انگلیسی است.

همچنین تضمین می‌شود یال‌های داده شده تشکیل یک درخت می‌دهند. در خط آخر، رشته $s$ که تنها از حروف کوچک انگلیسی تشکیل شده است، به شما داده می‌شود.

خروجی🔗

در تنها خط خروجی دو عدد جدا شده توسط یک فاصله چاپ کنید که به ترتیب نشان دهنده راس شروع مسیر و راس انتهای مسیر هستند. در صورتی که چنین مسیری وجود ندارد، -1 -1 چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

4
1 2 a
2 3 b
3 4 c
bc

خروجی نمونه ۱🔗

2 4

ورودی نمونه ۲🔗

4
1 2 a
2 3 b
3 4 c
ac

خروجی نمونه ۲🔗

-1 -1