+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- > *کِوین* در حال جستجوی بازی‌ در موتور جستجوی هوشمند خرید *ترب* بود، که بالاخره بازی‌ مورد علاقه‌اش را پیدا کرد. بازی این‌گونه است: ما در یک جدول نامتناهی (از هر طرف)، قرار داریم که رنگ تمام خانه‌ها به غیر از خانه‌ی $(0, 0)$ سفید رنگ است و رنگ خانه‌ی $(0, 0)$ قرمز است. ابتدا ما در خانه‌ی $(0, 0)$ قرار داریم و در هر مرحله می‌توانیم به یکی از چهار جهت بالا، راست، چپ، پایین برویم و به هر خانه که برویم رنگ آن خانه قرمز می‌شود (می‌توانیم یک خانه را بیش از یک بار ببینیم، ولی رنگ آن قرمز می‌ماند). حداکثر مساحت بین زیرمجموعه‌های ماکسیمال هم‌بند از خانه‌‌های سفید که تمامی خانه‌های آن در بین خانه‌های قرمز محصور باشد، برابر *امنیت* حرکات ما است. حال *کِوین* به شما یک روش حرکت در جدول را داده‌است و از شما می‌خواهد که *امنیت* حرکات را بدست آورید. * یک زیرمجموعه از خانه‌های سفید جدول را هم‌بند می‌نامیم اگر بین هر دو خانه از آن حداقل یک مسیر وجود داشته باشد. یک مسیر از خانه $a$ به خانه $b$ دنباله‌ای از خانه‌ها است که عضو اول دنباله خانه $a$ و عضو آخر دنباله خانه $b$ باشد، تمام خانه‌های درون دنباله عضو زیرمجموعه باشند و هر دو خانه متوالی‌ در دنباله مجاور ضلعی یکدیگر باشند. * یک زیرمجموعه ماکسیمال از خانه‌های سفید جدول زیرمجموعه‌ هم‌بندی است که خانه‌های آن میان خانه‌های قرمز محصور باشند. برای درک بهتر سوال به مثال‌ها توجه کنید. # ورودی در تنها خط ورودی رشته‌ی $s$ داده‌می‌شود که هر خانه از آن: * اگر `R` باشد یعنی حرکت به سمت راست است. * اگر `L` باشد یعنی حرکت به سمت چپ است. * اگر `D` باشد یعنی حرکت به سمت پایین است. * اگر `U` باشد یعنی حرکت به سمت بالا است. $$1 \le |s| \le 400 \ 000$$ منظور از $|s|$ طول رشته‌ی $s$ است. # خروجی در تنها خط خروجی *امنیت* حرکات را خروجی دهید. # مثال ## ورودی نمونه ۱ ``` RDRURDRDLU ``` ## خروجی نمونه ۱ ``` 0 ``` توضیح: حرکات به این شکل می‌شود: (`.` همان خانه‌های سفید است و ‍`R` خانه‌های قرمز است و ‍`S` نقطه‌ی شروع است) ``` .......... .......... .......... .......... ....SRRR.. .....RRRR. .......RR. .......... .......... .......... ``` ## ورودی نمونه ۲ ``` RRRRDDLLUDLLUUUURRRD ``` ## خروجی نمونه ۲ ``` 2 ``` توضیح: حرکات به این شکل می‌شود: (`.` همان خانه‌های سفید است و ‍`R` خانه‌های قرمز است و ‍`S` نقطه‌ی شروع است) ``` .......... ..RRRR.... ..R..R.... ..SRRRR... ..R.R.R... ..RRRRR... .......... .......... .......... .......... ``` ## ورودی نمونه ۳ ``` RDDLLU ``` ## خروجی نمونه ۳ ``` 1 ``` توضیح: حرکات به این شکل می‌شود: (`.` همان خانه‌های سفید است و ‍`R` خانه‌های قرمز است و ‍`S` نقطه‌ی شروع است) ``` ........ ........ ...SR... ..R.R... ..RRR... ........ ........ ``` ## ورودی نمونه ۴ ``` RRRRUUUULLLLDDDDDDDLLLUUURRR ``` ## خروجی نمونه ۴ ``` 9 ``` توضیح: حرکات به این شکل می‌شود: (`.` همان خانه‌های سفید است و ‍`R` خانه‌های قرمز است و ‍`S` نقطه‌ی شروع است) ``` ............ ............ .....RRRRR.. .....R...R.. .....R...R.. .....R...R.. ..RRRSRRRR.. ..R..R...... ..R..R...... ..RRRR...... ............ ............ ``` این شکل تنها دو زیرمجموعه هم‌بند ماکسیمال دارد که اندازه یکی ۹ و دیگری ۴ است. پس *امنیت* آن برابر ۹ می‌شود.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- بعد از بیش از دو سال انتظار و جستجو برای هم تیمی، ابواسحاق متوجه شد کدکاپ ۵ انفرادی برگزار می‌شود! برای همین کلی ناراحت شد و رشته افکارش تبدیل به گراف شد! اکنون برای باز گرداندن آن به حالت عادی، دست به دامن شما شده است. رشته افکار ابواسحاق یک گرافِ سادهٔ همبند $n$ راسی و $m$ یالی است. او تصمیم دارد برای بازگرداندن رشته افکارش در طی $k$ مرحله، هر مرحله یک یال به آن اضافه کند به طوری که گراف حاصل، ساده باقی بماند و دارای حداقل یک دور به طول فرد باشد. (گراف ساده گرافی است که دارای [یال چندگانه](https://fa.wikipedia.org/wiki/%DA%AF%D8%B1%D8%A7%D9%81_%DA%86%D9%86%D8%AF%DA%AF%D8%A7%D9%86%D9%87) و [طوقه](https://fa.wikipedia.org/wiki/%D8%AD%D9%84%D9%82%D9%87_%28%D9%86%D8%B8%D8%B1%DB%8C%D9%87_%DA%AF%D8%B1%D8%A7%D9%81%29) نباشد) امّا او که سلامت روانش بسیار برایش مهم است، قبل از این که دست به کار شود از شما می‌خواهد تا تعداد روش‌های مختلف انجام این عمل را به او بگویید. از آنجا که تعداد حالات، ممکن است بسیار زیاد باشد، باقی ماندهٔ تقسیم آن بر $10^{9} + 7$ را به او بگویید (دو روش از انجام $k$ مرحله را متمایز گوییم، اگر مرحله‌ای مثل $i$ وجود داشته باشد که دو سر یال اضافه شده در روش اول برابر با دو سر یال اضافه شده در روش دوم نباشد). **دقت کنید که ترتیب اضافه کردن $k$ یال اهمیت دارد.** # ورودی در خط اول ورودی سه عدد $n$، $m$ و $k$ آمده است. در $m$ خط بعدی دو عدد $v$ و $u$ آمده است، که نشان می‌دهد یک یال بین رئوس $v$ و $u$ وجود دارد. $$3 \le n \le 1\ 000$$ $$n-1 \le m < {n \choose 2}$$ $$1 \le v, u \le n$$ $$m + k \le {n \choose 2}$$ $$1 \le k$$ **تضمین می‌شود گراف ورودی، گرافی همبند و ساده است.** # خروجی در خروجی باید باقی‌مانده تعداد روش‌های خواسته شده بر $10^{9} + 7$ را چاپ کنید. ## ورودی نمونه ۱ ``` 4 3 2 1 2 2 3 3 4 ``` ## خروجی نمونه ۱ ``` 6 ``` <details> <summary>توضیحات مثال</summary> حالت های معتبر به شکل زیر هستند: $${(1, 3), (1, 4)}$$ $${(1, 3), (2, 4)}$$ $${(1, 4), (2, 4)}$$ $${(1, 4), (1, 3)}$$ $${(2, 4), (1, 3)}$$ $${(2, 4), (1, 4)}$$ هر سطر نشان دهندهٔ یک حالت از انجام $k$ مرحله است. ($(i, j)$ نمایانگر کشیدن یال بین دو رأس $i$ و $j$ است و یال‌ها را در هر سطر از چپ به راست اضافه می‌کنیم) </details> ## ورودی نمونه ۲ ``` 3 2 1 1 2 1 3 ``` ## خروجی نمونه ۲ ``` 1 ``` تنها می‌توان یال $(2, 3)$ را اضافه کرد.

+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- آی مجری که به فکر بچه‌ها است، تصمیم گرفته برای اولین بار آن‌ها را به سینما ببرد. آی مجری می‌داند که اگر یکی از بچه‌ها هنگام دیدن فیلم ناراحت باشد، فیلم را به کام همه تلخ خواهد‌کرد. به همین دلیل می‌خواهد همه راحت باشند. و اگر چنین چیزی امکان نداشت اصلا به سینما نروند. یکی از بچه‌‌ها ناراحت است اگر فردی جلوی او(نزدیک تر به پرده‌ی سینما و هم‌ستون با او) نشسته باشد و قدش از او بلندتر باشد. همچنین به دلیل این که آن‌ها خیلی خوش‌قلب هستند اگر بیننده‌ی دیگری غیر از آن‌ها هم نتواند فیلم را به خوبی ببیند(فرد بلندتری جلویش نشسته باشد)، ناراحت می‌شوند. همه‌ی انسان‌ها در سه دسته‌ی قدی دسته‌بندی می‌شوند: ۱) انسان‌های کوتاه(تا ۱۹۰ سانتی‌متر) ۲) انسان‌های معمولی(۱۹۱-۱۹۸سانتی‌متر) ۳) انسان‌های بلند(۱۹۹ به بالا) در واقع افرادی نمی‌توانند درست ببینند که یک نفر از دسته‌ی بلند‌تر جلوی آن‌ها نشسته باشد. صندلی‌های سینما $r$ ردیف و $c$ ستون دارند که در ردیف آخر نزدیک ترین آدم‌ها به پرده‌ی سینما نشسته‌اند. قبل از رسیدن بچه‌ها تعدادی بیننده به سالن سینما رفته اند و در جاهای دلخواه خود نشسته‌اند و نمی‌توان جای آن‌ها را تغییر داد. شما باید یک ترتیب دلخواه از نشستن همه‌ی بچه‌ها در سینما خروجی دهید که همگی راحت باشند و یا این که بگویید بهتر است اصلا به سینما نروند و به جای آن به پارک بروند. # ورودی در سطر اول ورودی دو عدد طبیعی $r$ و $c$ آمده‌است، که به ترتیب نمایانگر تعداد ردیف‌ها و ستون‌های سینماست. سپس در $r$ سطر بعدی در هر کدام $c$ کاراکتر آمده‌است که به این نحو معنی می‌شوند: ۱) جای خالی: # ۲) انسان کوتاه: s ۳)انسان معمولی: n ۴)انسان بلند: t در سطر بعدی سه عدد طبیعی و کوچکتر از یک میلیون می‌آید که به ترتیب نشان‌دهنده‌ی تعداد بچه‌های کوتاه، معمولی و بلند است که آی مجری می‌خواهد با خود به سینما بیاورد. $$1 \le r, c \le 1000$$ # خروجی اگر حالتی وجود نداشت، "Let's go to the park" را چاپ کنید. در غیر این صورت باید یک جدول مانند ورودی چاپ کنید که همه‌ی بچه‌ها نیز در جاهای خالی آن نشسته‌اند. اگر چند حالت وجود داشت،‌ به دلخواه یکی را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 3 3 ### #s# n## 2 1 1 ``` ## خروجی نمونه ۱ ``` t## ns# nss ``` قبل از رسیدن آی مجری و بچه‌ها دو نفر با قد‌های کوتاه و متوسط روی صندلی‌ها نشسته‌اند. فرد با قد متوسط در نزدیک ترین فاصله به پرده نشسته‌است. آی مجری ۴ نفر را با خود برده است. دو نفر با قد کوتاه، یک نفر با قد متوسط و یک نفر با قد بلند. یک حالت دلخواه از نشستن بچه‌ها را در خروجی می‌بینید. ## ورودی نمونه ۲ ``` 4 4 #### ##tn nt#s ##t# 4 3 2 ``` ## خروجی نمونه ۲ ``` Let's go to the park ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- **دوره ۱۰۲۸ ایا**، **دوره ۲۸ ایا** را بسیار خفن می‌پنداشتند(زیرا **دوره ۲۸ ایا** واقعا خفن بودند). اعتقاد **دوره ۱۰۲۸ ایا** به خفونت **دوره ۲۸ ایا** چنان بود که فکر می‌کردند **دوره ۲۸ ایا** می‌توانستند حتی مساله توقف را حل کنند! مساله توقف ( به انگلیسی : Halting problem ) مطرح می کند که آیا می توان برنامه ای نوشت که یک برنامه از ورودی بگیرد و تعیین کند که آیا برنامه متوقف می شود یا خیر. ثابت شده که در حالت کلی، الگوریتمی برای حل این مساله وجود ندارد. مسئول **دوره ۱۰۲۸ ایا** برای اینکه اعتماد به نفس **دوره ۱۰۲۸ ایا** تقویت شود، نسخه ساده شده‌ای از مساله هالت را به آنها داد تا آنها فکر کنند مثل **دوره ۲۸ ایا** خفن هستند. در این نسخه‌ ساده شده سه نوع دستور موجود است: ``` assign a = b + c cout a goto l ``` که در آن $a$ و $b$ و $c$ یک **حرف کوچک انگلیسی** (که نام یک متغیر است) یا یک **عدد یک رقمی** هستند و $l$ شماره خطی از برنامه است. تضمین می‌شود که بعد از `assign` متغیر `a` همیشه یک حرف کوچک انگلیسی است. شما باید خط به خط برنامه را دنبال کنید، در صورتی که برنامه پایان‌ناپذیر است، $-1$ را چاپ کنید. در غیر این‌صورت خروجی این برنامه را چاپ کنید. در این برنامه `cout` به معنای چاپ کردن یک عدد یا یک متغیر است. `goto` به معنای پرش به یک خط خاص است (خط‌ها از ۱ شماره‌گذاری شده‌اند). `assign a = b + c` یعنی $b+c$ را در متغیر $a$ قرار بده. هر حرف کوچک انگلیسی نشان‌دهنده یک متغیر است و محتوای همه‌ متغیرها در ابتدا صفر می‌باشد. با توجه به اینکه جواب مسئله ممکن است بزرگ شود شما باید **باقی مانده خروجی بر $10^9+7$** را بگویید. # ورودی در ورودی یک برنامه به شما داده می‌شود. در خط اول $n$ تعداد خط‌های برنامه و در $n$ خط بعد در هر خط یک دستور از برنامه داده می‌شود. $$1 \le l \le n \le 100\ 000$$ # خروجی اگر برنامه داده‌شده تمام نمی‌شود، در تنها سطر خروجی $-1$ چاپ کنید. در غیر اینصورت خروجی‌های برنامه‌ (به ازای هر `cout`) را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 2 assign a = 2 + 2 cout a ``` ## خروجی نمونه ۱ ``` 4 ``` ## ورودی نمونه ۲ ``` 4 assign a = 1 + 0 cout a assign a = a + a goto 2 ``` ## خروجی نمونه ۲ ``` -1 ``` ## ورودی نمونه ۳ ``` 7 cout 0 goto 5 cout 1 goto 7 cout 2 goto 3 cout 3 ``` ## خروجی نمونه ۳ ``` 0 2 1 3 ```