+ محدودیت زمان: ۳ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- > *کِوین* در حال جستجوی بازی‌ در موتور جستجوی هوشمند خرید *ترب* بود، که بالاخره بازی‌ مورد علاقه‌اش را پیدا کرد. بازی این‌گونه است: ما در یک جدول نامتناهی (از هر طرف)، قرار داریم که رنگ تمام خانه‌ها به غیر از خانه‌ی $(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...... ............ ............ ``` این شکل تنها دو زیرمجموعه هم‌بند ماکسیمال دارد که اندازه یکی ۹ و دیگری ۴ است. پس *امنیت* آن برابر ۹ می‌شود.

حل سؤال در بانک سؤالات