+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر شماست. بنابراین به ما تاکید کرد که حتما سوالی ساده به عنوان سوال اول به شما بدهیم. از آنجایی که ایشان حق بزرگتری به گردن ما دارند، ما حرفشان را اطاعت می‌کنیم: یک عدد به شما داده شده است. به تعداد آن عدد برای ما جمله‌ی "man khoshghlab hastam" را چاپ کنید بلکه به خوش‌قلب شدن، قدمی دیگر نزدیک شده باشید. # ورودی در تنها سطر ورودی یک عدد $n$ به شما داده شده است که نماینگر تعداد دفعاتی است که باید جمله‌ی فوق را چاپ کنید. $$ 1 \le n \le 100 $$ # خروجی خروجی شامل $n$ سطر می‌باشد که هر کدام از این سطر ها باید شامل عبارت "man khoshghlab hastam" باشد. # مثال ## ورودی نمونه ``` 3 ``` ## خروجی نمونه ``` man khoshghlab hastam man khoshghlab hastam man khoshghlab hastam ```

+ محدودیت زمان: ۰.۵ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر پروفسور باقر (که یک کاربر ناشی است) هم می‌باشد. پروفسور باقر یک ساعت دیواری نو خریده است و آن را در جایی قرار داده است که هنگامی که تلویزیون می‌بیند، از آینه بتواند آن ساعت را ببیند و بفهمد که ساعت چند است و چقدر مانده است تا مسابقه‌ی ایران در المپیک شروع شود. اما متاسفانه او بلد نیست که از آینه ساعت را بخواند. آقای خوش‌قلب به کمک پروفسور رفته است (البته به صورت مجازی) و می‌خواهد به او بگوید که ساعت چند است. پروفسور از طریق ایمیل برای آقای ‌خوش‌قلب، تصویری را که در آینه می‌بیند ارسال کرده است. آقای خوش‌‌قلب (از آنجایی که فقط خوش‌قلب است) نمی‌تواند از روی اطلاعاتی که پروفسور به او داده است، بفهمد که ساعت چند است. او از شما می خواهد که این کار را انجام دهید. ساعت پروفسور به شکل زیر (در این تصویر این ساعت، ساعت ۰۰:۰۰ را نشان می‌دهد) است و دو ویژگی دارد: ۱. عقربه‌ی ساعت شمار آن فقط روی اعداد صحیح می‌ایستد و (برعکس ساعت‌های عادی) به هیچ وجه بین شماره‌های ساعت توقفی ندارد. برای مثال زمانی که ساعت در بازه‌ی (۵:۰۰,۶:۰۰] است، عقربه‌ی ساعت شمار دقیقا روی شماره‌ی ۵ قرار دارد اما به محض اینکه ساعت ۶:۰۰ شود، عقربه ساعت شمار در یک حرکت انفجاری به سرعت به روی شماره‌ی ۶ می‌رود و تا زمانی که ساعت ۷:۰۰ شود، به روی آن می‌ماند و کوچکترین تکانی نمی‌خورد. ۲. شماره‌های این ساعت (مانند ساعت زیر) با اعداد مشخص نشده‌اند.  # ورودی در سطر اول ورودی به ترتیب دو عدد $a$ و $b$ آمده است که نشان‌دهنده‌ی این است که در تصویری که پروفسور برای آقای خوش‌قلب ارسال کرده است، ساعت چند است. بدین صورت که $a$ نمایانگر مکانی است که در تصویر ارسالی از پروفسور، عقربه‌ی ساعت شمار در آن قرار دارد و $b$ مکانی است که عقربه‌ی دقیقه شمار در آن قرار دارد. از آنجایی که المپیک نیمه شب از تلویزیون پخش می‌شود، ساعت حتما بیشتر مساوی ساعت ۰۰:۰۰ نیمه شب و اکیدا کمتر از ساعت ۱۲:۰۰ ظهر است یعنی بازه ی (۰۰:۰۰,۱۲:۰۰] $$ 0 \le a \le 11 $$ $$ 0 \le b \le 59 $$ # خروجی در تنها سطر خروجی با استفاده از تصویر ساعت در آینه، خروجی دهید که ساعت واقعاً چند است. خروجی شما باید به این شکل باشد: $$ hh:mm $$ یعنی در دورقم اول مکان عقربه‌ی ساعت شمار و سپس یک دو نقطه و سپس مکان عقربه‌ی دقیقه شمار را خروجی دهید. اگر مکان عقربه‌ی ساعت شمار یا عقربه‌ی دقیقه شمار یک رقمی بود، به جای رقم سمت چپ 0 خروجی دهید. برای مثال اگر ساعت ۹:۰۵ بود، شما باید "09:05" خروجی دهید. دقت کنید که خروجی حتما باید در بازه‌ی (۰۰:۰۰,۱۲:۰۰] باشد یا به عبارتی دیگر: $$ 0 \le hh \le 11$$ $$ 0\le mm \le 59 $$ # مثال ## ورودی نمونه ۱ ``` 3 55 ``` ## خروجی نمونه ۱ ``` 09:05 ``` ## ورودی نمونه ۲ ``` 0 0 ``` ## خروجی نمونه ۲ ``` 00:00 ```

+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر همه است؛ حتی به فکر افراد معتاد. برای همین او از همه‌ی معتاد‌های سراسر کشور دعوت کرده که به پیش او بروند تا فکری به حالشان بکند. اولین معتاد امروز به پیش آقای خوش‌قلب رفت. آقای خوش‌قلب ابتدا باید "سطح اعتیاد" این فرد را معین کند. برای این کار، از شخص معتاد یک تست گرفته شد. آقای خوش‌قلب تعداد خیلی زیادی جسم روی میز گذاشت و به معتاد گفت که اجسام یکسان را بشمرد و روی کاغذی بنویسد از هر جسم چندتا روی میز موجود است. آقای خوش‌قلب سطح اعتیاد افراد را بصورت عددی طبیعی مشخص می‌کند و می‌دانیم که یک معتاد با سطح اعتیاد $k$، هر جسم روی میز را $k$بار می‌بیند. (پس به ازای هر جسم موجود عددی که روی کاغذ می‌نویسد $k$ برابر تعداد واقعی است.) حال آقای خوش‌قلب به خانه‌ی خود رفته و حین دیدن بازی‌های پرهیجان المپیک، می‌خواهد که سطح اعتیاد معتاد را بدست آورد. اما ناگهان متوجه می‌شود که یادش نمی‌آید چه تعداد از هر جسم روی میز بوده! با شتاب به سوی کیف خود رفته و برگه‌ی نوشته‌های معتاد را بیرون می آورد. او با تمام خوش‌قلبی خود، می‌خواهد بفهمد که حداقل چند جسم روی میز بوده است تا کمترین مقدار هزینه به مسئول چیدمان اجسام روی میز بدهد! (کمی خسیس هم هست) حال خوش‌قلب به سراغ شما آمده و با دادن اعداد نوشته‌شده روی کاغذ معتاد به شما، از شما می‌خواهد که بگویید کمترین مقدار ممکن برای تعداد اجسام روی میز چه قدر میتوانسته باشد. # ورودی در سطر ورودی یک عدد $n$ آمده است که نمایانگر تعداد اعداد روی کاغذ معتاد است. (که برابر تعداد اجسام مختلف روی میز است.) سپس در سطر دوم ورودی $n$ عدد آمده است که با فاصله از هم جدا شده‌اند و نمایانگر اعداد نوشته شده روی کاغذ هستند. $$ 1 \le n \le 1\ 000\ 000 $$ اعداد روی کاغذ کوچکتر مساوی $1\ 000\ 000\ 000$ هستند. # خروجی خروجی باید شامل یک عدد باشد که برابر کمترین تعداد اجسام ممکن روی میز است. # مثال ## ورودی نمونه ۱ ``` 3 5 5 10 ``` ## خروجی نمونه ۱ ``` 4 ``` اگر سطح اعتیاد معتاد برابر ۵ باشد، می‌توان گفت روی میز ۴ جسم بوده‌ است که ۲ تای آن یک شکل بودند. ## ورودی نمونه ۲ ``` 3 1 2 3 ``` ## خروجی نمونه ۲ ``` 6 ``` چون معتاد از یکی از اجسام تنها یک دانه دیده، سطح اعتیاد او تنها می‌تواند ۱ باشد پس همه‌ی اجسام گفته‌شده توسط معتاد روی میز موجود هستند؛ سه نوع جسم و از نوع اول یک دانه، از نوع دوم ۲ تا و از نوع سوم، ۳ تا.

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- همانطور که از اسمش بر می‌آید، خوش‌قلب به فکر آدم‌های بیکار هم هست. از این رو بر آن شده است تا اداره ای تاسیس کند و $n$ نفر را در آن استخدام کند. او الان در مرحله‌ی طراحی روند اداری این اداره است. او مرتبه‌ی اداری افراد را به صورت زیر چیده است: کارمند‌ها را به ترتیب ورود به شرکت، با اعداد طبیعی ۱ تا $n$ شماره‌گذاری کرده‌ایم. هرکس که به شرکت وارد میشود زیردست نفراتی میشود که قبلا وارد شرکت شده اند(نفر اول زیردست کسی نیست)؛ بنابراین کارمند شماره ۲ زیردست کارمند شماره ۱ است، کارمند شماره ۳ زیردست کارمند شماره ۲ و ۱ است، و ... . متاسفانه او به اندازه‌ی کافی پول ندارد تا بتواند وسایل تفریحی کافی برای شرکت بخرد. برای همین او تصمیم گرفته است که به کارمندان اجازه دهد که به هم پس گردنی بزنند!! البته هر کسی نمی‌تواند به هر کسی پس گردنی بزند بلکه یک فرد فقط به آن دسته از زیر دستانش می‌تواند پس گردنی بزند که قدشان از او کوچکتر باشد. از آنجایی که آقای خوش‌قلب آدم خاصی است، سلیقه‌ی خاصی هم دارد. او می‌خواهد قد افرادش اعداد طبیعی بین ۱ تا $n$ باشد و در عین حال قد هیچ دو نفری یکسان نباشد. همچنین او می‌خواهد افراد طبق سلیقه‌ی او بتوانند به هم پس گردنی بزنند؛ یعنی او به ازای هر دو نفری می‌گوید که آیا دوست دارد آن شخصی که مرتبه‌اش از آن یکی بالاتر است بتواند به او پس گردنی بزند یا نه. برای مثال فرض کنید که او بخواهد که کارمند شماره ۱ بتواند به کارمند شماره ۳ پس گردنی بزند. در این صورت او باید طوری افراد را استخدام کند به طوری که قد کارمند شماره ۱ از کارمند شماره ۳ بیشتر باشد. قد کارمند شماره $i$ را $h_i$ می‌نامیم. حالا آقای خوش‌قلب سلیقه‌اش را به شما می‌دهد و از شما می‌خواهد که به او بگویید که به ازای هر $i$، قد نفری که برای پست $i$ـم استخدام می‌شود باید چقدر باشد که در نهایت افراد مطابق سلیقه‌ی او بتوانند به هم پس گردنی بزنند. سلیقه‌اش را به صورت یک گراف جهتدار به شما می‌دهد به این صورت که او دوست دارد کارمند شماره $i$ بتواند به کارمند شماره $j$ ($i < j$) پس گردنی بزند اگر و تنها اگر در گرافی که به شما داده‌است، بین راس شماره $i$ و راس شماره $j$ یک یال جهتدار از $i$ به $j$ باشد. سلیقه‌ی آقای خوش‌قلب خاص است. پس سلیقه‌اش هم خاص است. پس گرافی که او به شما می‌دهد هم خاص است. این گراف دو ویژگی دارد: ۱. اگر در آن کارمند شماره $i$ به $j$ پس گردنی می‌زند و کارمند $j$ هم به $k$ پس گردنی می‌زند،‌($i < j < k$) حتما کارمند $i$ هم به $k$ پس گردنی می‌زند. (رابطه‌ی تعدی) ۲. هیچ یالی از بین دو راس طوری قرار نگرفته است که معنی اش این باشد که شخصی به بالا دستی اش پس گردنی بزند. مثلا هیچوقت یال جهتداری از راسی ۳ به راس ۱ وجود ندارد. به عبارتی دیگر هیچ یال جهتداری از راسی با شماره‌ی بزرگتر به راسی با شماره‌ی کوچکتر وجود ندارد. # ورودی در سطر اول ورودی دو عدد طبیعی $n$ و $m$ با فاصله از هم آمده است که نمایانگر تعداد کارمندها و تعداد پس‌گردنی‌های که هر روز زده می‌شود است. در هریک از $m$ سطر بعدی، به ترتیب دو عدد طبیعی $a$ و $b$ با فاصله آمده است که نشان میدهد آقای خوش‌قلب دوست دارد کارمند شماره $a$ به کارمند شماره $b$ پس‌گردنی بزند. $$ 1 \le n, m \le 100\ 000 $$ $$1 \le a < b \le n$$ تضمین می‌شود گراف ورودی دو شرط گفته شده را دارد. # خروجی اگر ورودی ها معتبر نبودند(شرکتی به این شکل وجود نداشت)، در تنها خط خروجی "No answer" چاپ شود. وگرنه در تنها سطر خروجی $n$ عدد با فاصله از هم چاپ کنید که که عدد $i$م نشان دهنده $h_i$ است در یک اداره‌ای که شرایط گراف گفته‌شده توسط خوش‌قلب را برقرار میکند. (یعنی نفر $a$ آن میتواند به $b$ پس‌گردنی بزند اگر و تنها اگر در گراف راس $a$ به $b$ یال داشته باشد.) # مثال ## ورودی نمونه ۱ ``` 2 1 1 2 ``` ## خروجی نمونه ۱ ``` 2 1 ``` ## ورودی نمونه ۲ ``` 3 2 1 2 1 3 ``` ## خروجی نمونه ۲ ``` 3 1 2 ```