+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کریم یک کودک ۵ ساله است که به اسم متغیرها خیلی توجه می‌کند. کریم یک پدربزرگ دارد که از «واج آرایی» متنفر است. او اسم‌هایی را دوست دارد که در آن‌ها تعداد حرف‌های مختلف زیاد باشد. برای مثال karim پنج حرف مختلف (همه‌ی حرف هایش مختلفند) و abbas سه حرف مختلف دارد. (حرف های a و b و s) کریم در انتخاب اسم برای یک متغیر در کدش به مشکل خورده و بین $n$ اسم موجود شک دارد. او این اسامی را به پدربزرگش می‌دهد تا بهترین اسم را برگزیند. میدانیم که پدربزرگ اسمی را انتخاب می‌کند که بیشترین تعداد حروف مختلف را دارد. با داشتن این اسامی، بگویید که تعداد حروف مختلف در اسم انتخابی پدربزرگ چقدر خواهد بود. # ورودی خط اول ورودی شامل عدد $n$ است. در $n$ خط بعدی هر خط شامل یک اسم پیشنهادی است. هر اسم رشته‌ای با حداکثر ۲۰ حرف از حروف کوچک انگلیسی می‌باشد. # خروجی در تنها خط خروجی یک عدد چاپ کنید که برابر تعداد حروف مختلف در اسم انتخابی خواهد بود. # ورودی نمونه ``` 4 ali karim abbas mohammad ``` # خروجی نمونه ``` 5 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- کریم یک کودک ۵ ساله است که در گفتن برخی حروف انگلیسی مشکل دارد. برای مثال او گاهی از اوقات به جای حرف K، حرف T را تلفظ میکند. اما او هیچ‌گاه به جای حرف T، حرف K را تلفظ نمی‌کند. همینطور او گاهاَ حرف G را به اشتباه D تلفظ می‌کند. و R را بعضی اوقات L تلفظ می‌کند و بعضی اوقات F. البته پیش می‌آید که این حروف را درست تلفظ کند. مادر کریم همیشه نسبت به گفته‌ی او شوق وافری نشان می‌دهد؛ از این رو کلمه‌ای که کریم گفته را به شما میگوید و شما باید تعداد کلمه‌های ممکن که کریم با مدنظر داشتن آن‌ها چنین کلمه‌ای را می‌گوید را به او بگویید. (مستقل از بامعنا بودن یا نبودن این کلمات) به مثال و توضیح آن توجه کنید. # ورودی تنها خط ورودی شامل یک رشته به طول حداکثر ۲۰ حرف از حروف بزرگ انگلیسی است. # خروجی تنها خط خروجی باید شامل یک عدد باشد که برابر با جواب مسئله است. # ورودی نمونه ``` FILIPEK ``` # خروجی نمونه ``` 4 ``` کریم ممکن است کلمات FILIPEK، RILIPEK، RIRIPEK یا FIRIPEK را مد نظر داشته باشد.

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک جنازه‌ در پارک ملت پیدا شده است. طبق گفته‌های پزشک قانونی، مقتول به وسیله‌ی شات-گان کشته شده و شلیک گلوله‌ی شات-گان در یک لحظه بین لحظه‌ی $L$ و لحظه‌ی $R$ (شامل این دو لحظه) اتفاق افتاده است. کاراگاه شمس می‌خواهد حداقل و حداکثر تعداد ممکن برای افراد حاضر در پارک هنگام شلیک گلوله را بداند. همکار کارآگاه شمس، مادام، لیستی از مظنونین تهیه کرده و طی بازپرسی متوجه شده که مظنون $i$ام از لحظه‌ی $l_i$ تا لحظه‌ی $r_i$(شامل این دو لحظه)، در پارک حضور داشته است. مادام می‌خواهد با استفاده از این اطلاعات اعداد مدنظر کاراگاه شمس را به او بگوید. البته این کار ساده‌ای نیست، پس به او کمک کنید! **شلیک میتواند در لحظه‌ای اعشاری اتفاق بیفتد.** # ورودی خط اول ورودی شامل دو عدد $L$ و $R$ است. خط دوم شامل عدد $n$ است که بیانگر تعداد مظنونین واقعه می‌باشد. سپس در $n$ خط بعد هریک شامل دو عدد $l_i$ و $r_i$ است. $$0 \le L \le R \le 10^9$$ $$0 \le l_i \le r_i \le 10^9$$ $$1 \le n \le 5000$$ # خروجی تنها خط خروجی باید شامل دو عدد باشد که برابر با کمترین و بیشترین تعداد ممکن برای افراد حاضر در لحظه‌ی شلیک شات-گان هستند. # ورودی نمونه ``` 6 10 4 1 8 6 8 7 10 8 9 ``` # خروجی نمونه ``` 1 4 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۶۴ مگابایت ---------- کریم یک کودک ۵ ساله است و در گردهمایی مهدکودکی‌ها شرکت می‌کند. کریم و $n - 1$ نفر از هم مهدی‌هایش دور یک میز دایره‌ای شکل جهت صرف دوغ گرد هم آمده‌اند. آن‌ها را با شروع از کریم و بصورت ساعتگرد، با اعداد 1 تا $n$ شماره‌گذاری می‌کنیم. بین برخی از این کودکان رابطه‌ی دوطرفه‌ی دوستی برقرار است. پس از انتظارهای بسیار، یک عدد پارچ دوغ به کنار میز آورده می‌شود. همه‌ی این $n$ نفر می‌خواهند از این دوغ بنوشند. روند دوغ‌رسانی در این قبیل گردهمایی‌ها به این صورت است که پارچ دوغ ابتدا به یکی از افراد دور میز داده می‌شود. هرکسی که پارچ به دستش میرسد پس از نوشیدن مقداری از آن، پارچ دوغ را به یکی از دوستانش که هنوز دوغ نخورده است می‌دهد تا وقتی که همه از آن بنوشند. دقت کنید که بخاطر سن کم، هیچ کس پارچ دوغ را به کسی که با او دوست نیست نمی‌دهد. به دلیل بزرگ بودن میز و کوچک بودن کودکان، هرکس برای رساندن دوغ به نفر بعدی به روی میز میرود و هنگام راه رفتن روی مسیر بین جایگاه نشستن خود و نفر بعدی، خطی از دوغ روی میز باقی می‌گذارد. روی هیچ نقطه‌ای از مسیری که یک کودک به سمت کودک بعدی طی می‌کند نباید از قبل دوغی ریخته شده باشد؛ چون کودک هنگام حمل دوغ لیز خورده و خاطره‌ی بدی از گردهمایی بجا خواهد ماند. حال با دانستن روابط دوستی بین این کودکان، بگویید که این ها به چه ترتیبی می‌توانند دوغ بخورند که به همه دوغ برسد و هیچکس هنگام حمل دوغ زمین نخورد. (یا بگویید که امکان ندارد.) # ورودی خط اول ورودی شامل عدد $n$ است. در خط دوم ورودی عدد $m$ که بیانگر تعداد رابطه های دوستی بین کودکان است. هریک از $m$ خط بعدی یک جفت عدد $u, v$ آمده که یعنی کودک شماره $u$ و کودک شماره $v$ با هم دوست هستند. $$3 \le n \le 1000$$ $$0 \le m \le \frac{n \times (n-1)}2$$ # خروجی اگر امکان ندارد که به همه با شرایط گفته شده دوغ برسد، تنها خط خروجی باید شامل عدد $-1$ باشد. در غیر این صورت خروجی برنامه باید ترتیبی صحیح از دوغ خوردن افراد باشد که در $n$ خط آمده است. در صورت وجود چند ترتیب درست، یکی را به دلخواه خروجی دهید. # ورودی نمونه ۱ ``` 7 9 1 4 5 1 1 7 5 6 2 3 3 4 2 6 4 6 6 7 ``` # خروجی نمونه ۱ ``` 2 3 4 1 7 6 5 ``` # ورودی نمونه ۲ ``` 4 3 1 2 2 4 1 3 ``` # خروجی نمونه ۲ ``` -1 ```

+ محدودیت زمان: ۳ ثانیه + **محدودیت حافظه: ۶ مگابایت** ---------- کریم یک کودک ۵ ساله‌ی علاقه‌مند به نقاشی است و عشق به نقاشی باعث شده که اکثر نقاشی‌های او بسیار طویل باشند. کریم نقاشی هایش را روی کاغذی شطرنجی می‌کشد و می‌توان آن‌ها را به صورت زیر توصیف کرد: + هر خانه‌ی شطرنجی یا کامل سیاه است و یا کامل سفید + از هر خانه‌ی سیاه به تمامی خانه‌های سیاه مسیر سیاه وجود دارد. مسیر سیاه یعنی دنباله‌ای از خانه‌های سیاه که هر دو خانه‌ی پشت سر هم از آن در ضلعی مشترک باشند. + هیچ سوراخ سفیدی در شکل وجود ندارد؛ یعنی از هر خانه‌ی سفید به خارج از نقاشی مسیر سفید وجود دارد. مسیر سفید یعنی دنباله‌ای از خانه‌های سفید که هر دو خانه‌ی پشت سر هم از آن در ضلعی مشترک باشند. کریم امروز طبق عادت هفتگی خود سراغ نقاشی رفت، اما به دلایل نامشخص فاز خستگی برداشت و تصمیم گرفت تنها دورگیری نقاشی‌اش را توصیف کند. به خانه‌ی سیاهی در نقاشی خانه‌ی گوشه‌ای میگوییم اگر در خانه‌های مجاور راسی آن (۸ خانه) حداقل یک خانه‌ی سفید وجود داشته باشد. دورگیری‌ای که کریم توصیف می‌کند بصورت دنباله‌ای از دستورات حرکتی است که با حروف انگلیسی متناظر شده‌اند. این توصیف با حرف P شروع می‌شود و با حرف K تمام می‌شود. بقیه‌ی دنباله از حروف E، N، W و S که به ترتیب دستور حرکت به غرب، شمال، شرق و جنوب هستند تشکیل شده است. کریم در دورگیری خود از یک خانه‌ی گوشه‌ای دلخواه شروع میکند و همه‌ی خانه‌های گوشه‌ای نقاشی مدنظرش را طی می‌کند و به خانه‌ی شروع بازمیگردد. در مسیر حرکت همه‌ی خانه‌های دیده شده خانه‌های سیاه گوشه‌ای نقاشی خواهند بود. می‌دانیم که کریم دورگیری خود را به ترتیب عکس عقربه‌های ساعت انجام می‌دهد. مادر کریم همیشه نسبت به نقاشی‌های او هم شوق وافری نشان می‌دهد؛ از این رو پس از دیدن دورگیری او، تصمیم می‌گیرد که تعداد خانه‌های سیاه این نقاشی را به دست آورد. با مقدار اندکی حافظه به او کمک کنید! # ورودی ورودی شامل دنباله‌ی دورگیری داده شده توسط کریم است که هر حرف آن در خطی جداگانه آمده است. دنباله از حداکثر ۴۰۰۰۰۰۰ حرف تشکیل شده است. تضمین می‌شود که دنباله‌ی ورودی یک دورگیری صحیح است. # خروجی در تنها خط خروجی شما باید تعداد خانه‌های سیاه در نقاشی توصیف شده را خروجی دهید. # ورودی نمونه ``` P S S S E N E E S E E N N N N S S S W W N N W W W N S K ``` # خروجی نمونه ``` 23 ``` نقاشی خروجی نمونه به شکل زیر است: