+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *از آنجایی که هر روز درخواست بچه‌های دوره برای شام طلا بیشتر می‌شد، مجمع شازززیا هر $n$ عضوش را به یک جلسه‌ی سرّی فراخوند تا بتوانند نقشه‌ای بکشند که این داستان را تمام کنند.* هر کدام از شازززیا، نقشه‌ای داشتند و برای اینکه عادلانه تصمیم گیری کنند، در هر جلسه‌ای که بینشان صورت می‌گرفت: - هر کس که می‌خواست نقشه‌اش را ارائه بدهد، $p$ دقیقه زمان نیاز داشت. - برای اینکه رای گیری کنند و بین نقشه‌ها یکی را انتخاب کنند، $v$ دقیقه زمان لازم داشتند. برای مثال اگر در جلسه‌ای $100$ نفر حضور داشته باشند و ارائه نقشه هر کس یک دقیقه طول بکشد $(p = 1)$ و رای گیری هم یک دقیقه طول بکشد $(v = 1)$ جمعاً $100$ دقیقه ارائه نقشه‌ها طول می‌کشد و کلاً $101$ دقیقه که علاوه بر ارائه نقشه‌ها رای گیری هم کنند و یکی را انتخاب کنند. برای تسریع کارشان تصمیم گرفتند که به تعدادی گروه تقسیم شوند و گروه‌ها با هم به طور همزمان کار را پیش ببرند. هر گروه بهترین نقشه را بین اعضای خودش انتخاب می‌کند. بعد نماینده هر گروه نقشه منتخب آن گروه را ارائه می‌دهد و بین نقشه‌های منتخب ارائه شده یکی را انتخاب می‌کنند. برای مثال، اگه $100$ نفر به یک گروه $60$ نفره و یک گروه $40$ نفره تقسیم شوند: - گروه بزرگتر بعد از $61$ دقیقه بهترین نقشه اش را انتخاب می‌کند. - گروه کوچکتر بعد از $41$ دقیقه بهترین نقشه اش را انتخاب می‌کند. - نماینده دو گروه بعد $2$ دقیقه نقشه‌های منتخب گروهشان را ارائه می‌دهند و بعد از $1$ دقیقه رای گیری می‌کنند و بهترین نقشه را انتخاب می‌کنند. کل زمانی که طول کشیده است: $61 + 2 + 1 = 64$ دقیقه. لازم به ذکر است که خود گروه‌ها هم ممکن است به زیر گروه‌هایی تقسیم شوند و بعضی وقت‌ها هم ممکن است تقسیم شدن به بیشتر از دو گروه سودمندتر باشد. بعنوان یک حالت خاص، در یک زیرگروه با فقط یک عضو، تصمیم گیری و انتخاب یک نقشه زمانی نمی‌برد.(چون نیازی نیست نقشه اش را به خودش توضیح بدهد.) همه شازززیا از اولش می‌دانستند که قرار است نقشه آقاتیزی انتخاب شود (نقشه‌ای که در آن قرار است میان دعوای بچه‌ها سر تیم کشی فوتبال، خودش را طرف بچه‌های دوره جا بزند.) ولی آقاتیزی اصرار داشت که برای رعایت عدالت هم که شده، روال انتخاب نقشه به صورت رسمی خودش طی شود. حالا از آنجایی که شازززیا دارند نقشه می‌کشند و وقت کم دارند، از شما خواستند که به صورت خیلی سرّی برنامه‌ای برایشان بنویسید که به ازای ورودی گرفتن $n$ و $p$ و $v$، کمینه زمان که انتخاب بهترین نقشه طول می‌کشد را به آن‌ها بگید. # ورودی به ترتیب $n$ نشان دهنده تعداد افراد، $p$ نشان دهنده زمان مورد نیاز برای ارائه نقشه یک نفر بر حسب دقیقه و در نهایت $v$ نشان دهنده زمان مورد نیاز برای رای گیری بر حسب دقیقه در یک خط ورودی داده می‌شود. $$ 1 \le n \le 10^{15} $$ $$ 1 \le p, v \le 10^9 $$ # خروجی یک عدد خروجی داده شود که برابر کمینه زمان لازم برای انجام مراسم سرّی و انتخاب بهترین نقشه بر حسب دقیقه باشد. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۲۵ | $$ n \le 5\,000 \ \ \ \ \ p,\ v \le 1000 $$ | | ۲ | ۲۰ | $$ n \le 50\,000 \ \ \ \ p,\ v \le 1000 $$ | | ۳ | ۲۵ | $$ p,\ v \le 1000 $$ | | ۴ | ۳۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 9 1 1 ``` ## خروجی نمونه ۱ ``` 8 ``` توضیح نمونه: اعضا می‌توانند به $3$ گروه $3$ نفره تقسیم شوند بعد هر گروه $4$ دقیقه زمان می‌برد و در نهایت نماینده‌های سه گروه هم برای انتخاب نهایی $4$ دقیقه دیگر زمان نیاز دارند. بنابراین پاسخ نمونه برابر $4 + 4 = 8$ است. ## ورودی نمونه ۲ ``` 6 1 2 ``` ## خروجی نمونه ۲ ``` 8 ``` توضیح نمونه: در این نمونه تمام اعضا در یک گروه قرار دارند، $6$ دقیقه زمان ارائه و $2$ دقیقه زمان رای‌گیری لازم است. بنابراین پاسخ نمونه برابر $6 + 2 = 8$ است. ## ورودی نمونه ۳ ``` 6 2 1 ``` ## خروجی نمونه ۳ ``` 12 ``` توضیح نمونه: در این نمونه تمام اعضا به سه گروه دو نفره تقسیم می‌شوند. در هر گروه زمان لازم برای انتخاب بهترین نقشه برابر $5$ است. بعد از این سه نماینده گروه در مدت $7$ دقیقه بهترین نقشه را انتخاب می‌کنند. بنابراین پاسخ این نمونه برابر $5 + 7 = 12$ است.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *وقتی که بچه‌های دوره داشتند وارد رستوران می‌شدند دیدند که نه از شازززیا خبری هست نه از آقا تیزی، فهمیدند که سرشان کلاه رفته و افتادند دنبال شازززیا.* نقشه‌ی شازززلند به شکل یک جدول $ n \times m $ است که هر خانه از آن یا خیابان است یا ساختمان. شازززیا و بچه‌های دوره هم در دو خانه متفاوت قرار دارند. (طبیعتا فقط از خیابان‌ها می‌توان عبور کرد.) همه می‌دانند که یک خانه هم در نقشه هست که در آن یک پورتال، به یک دنیای آینه‌ای که شازززیا هم می‌خواهند به آن فرار کنند، وجود دارد. چون نقشه‌ی شازززلند با ماهواره رصد می‌شود، شازززیا نقشه را به صورت آنلاین در دسترس دارند و از آنجایی که بچه‌های دوره هم هکرهای ماهری هستند، می‌توانند به نقشه آنلاین دسترسی داشته باشند. شازززیا سوار یک ماشین شده‌اند که برای حرکت نیاز به یک کد ثابت دارد. (کدی از حرکات بالا، پایین، چپ یا راست) که اول کار باید کد را به آن بدهند. ماشین هم با توجه به آن کد حرکت می‌کند و دیگر کد قابل تغییر نیست. از آنجایی که در فرایند رای گیری برای انتخاب کد غوغایی به پا شد، بچه‌های دوره هم کدی که شازززیا به ماشین می‌دهند را می‌دانند. در هر ثانیه ماشین شازززیا یک حرکت در جدول می‌کند و بعد از آن در همان ثانیه بچه‌های دوره می‌توانند یا یک حرکت دلخواه بکنند یا سرجایشان بمانند. هر حرکت هم یعنی حرکت به یکی از خانه های مجاور ضلعی. (بالا، پایین، راست، چپ) در پایان هر ثانیه - اگه شازززیا و بچه‌های دوره در یک راستا (سطر یا ستون) قرار بگیرند که بینشان ساختمانی نباشد، بچه‌های دوره شازززیا را اسیر می‌کنند. - اگه شازززیا اسیر نشوند و به پورتال برسند، می‌توانند فرار کنند و دست بچه‌های دوره به آن‌ها نمی‌رسد. از آنجایی که هم بچه‌های دوره هم شازززیا در تعقیب و گریزند از شما انتظار می‌رود که برنامه‌ای بنویسید که مشخص کند آیا شازززیا می‌توانند اول کار کدی را به ماشینشان بدهند که به پورتال برسند و از دست بچه های دوره فرار کنند یا نه؟ # ورودی خط اول ورودی به ترتیب شامل $n$ و $m$ که نشان دهنده ابعاد نقشه شازززلند است، داده می‌شود. هر کدام از $n$ خط بعدی شامل رشته‌ای به طول $m$ است. هر حرف از آن رشته نشان دهنده یک خانه از جدول است که اگر `.` باشد یعنی خیابان است، اگر `B` باشد ساختمان است، اگر `D` باشد نشان دهنده جای بچه‌های دوره است، اگه `S` باشد نشان دهنده جای شازززیاست و در نهایت `P` هم پورتال است. $$ 1 \le n, m \le 700 $$ # خروجی در تنها خط خروجی `YES` چاپ کنید اگر شازززیا می‌توانند بدون اسیر شدن توسط بچه های دوره با تعیین یک کد اولیه برای ماشینشان به پورتال فرار کنند و در غیر آن `NO` چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۵۰ | $$ 1 \le n,m \le 200 $$ | | ۲ | ۵۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 5 7 S.....D ..B.... ..BBBBB ....... ...P... ``` ## خروجی نمونه ۱ ``` YES ``` توضیح نمونه: شازززیا می‌توانند با کد زیر موفق شوند: پایین - پایین - پایین - راست - راست - راست - پایین ## ورودی نمونه ۲ ``` 5 7 S....D. ..B.... ..BBBBB ....... ...P... ``` ## خروجی نمونه ۲ ``` NO ``` ## ورودی نمونه ۳ ``` 2 3 .SP DBB ``` ## خروجی نمونه ۳ ``` NO ``` توضیح نمونه: اگر همزمان شازززیا به پورتال برسند و بچه‌های دوره هم آن‌ها را ببینند (یعنی هر دو گروه در یک راستا که ساختمانی بینشان وجود ندارد باشند) باز هم شازززیا اسیر می‌شوند. در نمونه دوم و سوم هیچ کدی وجود ندارد که شازززیا را نجات دهد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *متاسفانه یا خوشبختانه شازززیا با موفقیت به پورتال رسیدند و به دنیای آینه‌ای وارد شدند و تصمیم گرفتند با هویت جدید غازززیا به ادامه زندگی بپردازند. آن‌ها متوجه شدند که در این دنیای جدید خیلی چیزها قرینه و پالیندروم است. بخاطر همین تصمیم گرفتند یک شهر پالیندرومی هم پیدا کنند و آن را پایتخت جدیدشان یعنی غازززلند بنامند.* به یک شهر می‌گوییم پالیندروم اگر شرایط زیر وجود داشته باشد: - درخت ریشه‌دار $T$ وجود داشته باشد و $S$ یک کپی از $T$ باشد طوری که گراف $G$ اجتماع $T$ و $S$ باشد و برگ‌های متناظر در $S$ و $T$ ادغام(مرج) شده باشند (اما ریشه اگه برگ باشد مرج نمی‌شود). در این صورت به گراف $G$ پالیندروم می‌گوییم. حالا اگر $G$ با نقشه آن شهر متناظر باشد، به آن شهر نیز پالیندروم می‌گوییم. از آنجایی که غازززیا با کلی شهر جدید رو به رو هستند به آن‌ها کمک کنید و برنامه‌ای بنویسید که بتوان با آن مشخص کرد که آیا یک گراف دلخواه همبند غیر جهت دار، پالیندروم هست یا نه؟  نمونه ای از یک شهر پالیندروم که مثال سوم را نشان می‌دهد. # ورودی خط اول ورودی $n$ نشان دهنده تعداد رئوس و $m$ نشان دهنده تعداد یال‌ها است. رئوس گراف با $1$ تا $n$ شماره گذاری شده‌اند. در $m$ خط بعدی یال‌ها آمده‌اند. در هر خط آن یک $x$ و یک $y$ آمده‌اند که به معنای وجود یال بین راس $x$ و $y$ است. ($x \neq y$ و $1 \leq x,y \leq n$) همچنین تضمین می‌شود که یال چندگانه نداریم. $$3 \le n, m \le 100000$$ # خروجی در تنها خط خروجی `YES` چاپ کنید اگر نقشه شهر ورودی (گراف ورودی) پالیندروم بود و در غیر آن `NO` چاپ کنید. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۳۰ | $$ 3 \le n,m \le 300 $$ | | ۲ | ۳۰ | $$ 3 \le n,m \le 3500 $$ | | ۳ | ۴۰ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 7 7 1 2 2 3 3 4 4 5 5 6 6 7 7 1 ``` ## خروجی نمونه ۱ ``` NO ``` ## ورودی نمونه ۲ ``` 6 6 1 2 2 3 2 4 3 5 4 5 5 6 ``` ## خروجی نمونه ۲ ``` YES ``` توضیح نمونه: درخت $1$ و $2$ و $3$ و $4$ متناظر با درخت $6$ و $5$ و $4$ و $3$ است. ## ورودی نمونه ۳ ``` 22 28 13 8 8 1 1 22 1 12 1 14 13 18 13 4 4 20 20 7 13 15 15 3 15 9 9 16 9 19 22 5 12 5 14 5 5 11 11 6 18 6 7 10 10 17 17 6 3 21 21 6 16 2 19 2 2 21 ``` ## خروجی نمونه ۳ ``` YES ``` توضیح نمونه: گراف این مثال در صورت سوال رسم شده است.