+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- پیمان به علی قول داده است که در آموزش درس الگوریتم دوره تابستان به او کمک خواهد کمک کرد. مشکل اینجاست که او در مشهد زندگی می‌کند و دوست ندارد مدت زیادی از خانه‌اش دور باشد. به همین دلیل علی از او خواسته تنها دو مبحث از $n$ مبحث درس الگوریتم را آموزش بدهد. درس الگوریتم $n$ مبحث دارد که هر کدام از مبحث‌ها ممکن است پیش‌نیاز تعدادی از مبحث‌های دیگر باشند. ترتیب آموزش مبحث‌ها در دوره‌ی تابستان مشخص نیست ولی می‌دانیم که روابط پیش‌نیازی در این ترتیب رعایت خواهند شد. (اگر مبحثی پیش‌نیاز یک مبحث دیگر باشد قطعاً زودتر آموزش داده می‌شود) هم‌چنین می‌دانیم که آموزش یک مبحث دقیقاٌ یک روز طول می‌کشد و طبق برنامه قرار است در طی $n$ روز تمامی مبحث‌های درس الگوریتم آموزش داده شود. پیمان در نظر دارد که در طی یک سفر دو روزه به تهران به قول خود عمل کند، دو مبحث در درس الگوریتم آموزش دهد، و به خانه برگردد. به همین خاطر او باید دو مبحث را به نحوی انتخاب کند که در هر ترتیبی از مبحث‌ها که برای آموزش الگوریتم انتخاب می‌شود، آن دو مبحث در دو روز متوالی در برنامه بیایند. هم‌چنین پیمان دوست ندارد مبحث‌هایی که آموزش می‌دهد نامرتبط باشند و می‌خواهد به شکلی آن دو مبحث را انتخاب کند که یکی از آن‌ها پیش‌نیاز دیگری باشد. او به چه روش‌هایی می‌تواند دو مبحث را با شرایط دلخواه‌ش انتخاب کند؟ # ورودی در خط اول ورودی دو طبیعی $n$ و $m$، نشان‌دهنده‌ی تعداد مبحث‌های درس الگوریتم و تعداد روابط پیش‌نیازی بین مبحث‌ها، آمده است. در $m$ خط بعدی ورودی، در هر خط دو عدد طبیعی $v_i$ و $u_i$ آمده است که نشان‌دهنده‌ی این است که مبحث ‌$v_i$ پیش نیاز مبحث $u_i$ است. تضمین می‌شود هر رابطه پیش‌نیازی بین دو مبحث حداکثر یک بار در ورودی آمده است. تضمین می‌شود ترتیبی برای آموزش مبحث‌ها وجود دارد که در آن تمام رابطه‌های پیش‌نیازی رعایت شده باشد. $$1 \le n, m \le 500\ 000$$ $$1 \le m \le \binom{n}{2}$$ $$1 \le v_i, u_i \le n, v_i \ne u_i$$ # خروجی در خط اول خروجی $k$ تعداد روش‌هایی که پیمان می‌تواند دو مبحث با شرایط گفته شده را انتخاب کند چاپ کنید. در $k$ خط بعدی خروجی در هر خط دو عدد $a_i$ و $b_i$ را چاپ کنید به طوری که مبحث $a_i$ پیش‌نیاز مبحث $b_i$ باشد و این دو مبحث یک روش دلخواه پیمان باشند. ترتیب خروجی باید به شکلی باشد که به ازای هر $i$ و $j$ که $i < j$، $a_i < a_j$ یا اگر $a_i = a_j$، $b_i < b_j$. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۹ | $n \le 9$ | | ۲ | ۲۱ | $n, m \le 1\ 000$ | | ۳ | ۱۷ | $n \le 1\ 000$ | | ۴ | ۵۳ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 4 1 2 1 3 2 4 3 4 ``` ## خروجی نمونه ۱ ``` 0 ``` ## ورودی نمونه ۲ ``` 6 5 1 2 2 3 3 4 3 5 5 6 ``` ## خروجی نمونه ۲ ``` 2 1 2 2 3 ``` ## ورودی نمونه ۳ ``` 4 6 4 3 4 2 4 1 3 2 3 1 2 1 ``` ## خروجی نمونه ۳ ``` 3 2 1 3 2 4 3 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- در تورنمنت جهانی «نان‌بیار، کباب‌ببر»، ورزشکاران با قدرت دستهایشان شناخته می‌شوند. در این مسابقات، $n$ ورزشکار شرکت‌ کرده‌اند که قدرت دست راست ورزشکار $i$-ام، $r_i$ و قدرت دست چپش $l_i$ است. در این مسابقات، در هر مرحله، مسابقه‌ای بین دو ورزشکار انجام می‌شود و فرد بازنده از تورنمنت حذف می‌شود. بنابراین بعد از $n-1$ مرحله، تنها یک فرد در تورنمنت باقی‌ می‌ماند که مدال طلای مسابقات را دریافت می‌کند. اگر مسابقه‌ای بین ورزشکار $i$ و $j$ انجام شود، ورزشکار $i$ شانس پیروزی در این مسابقه را دارد اگر $l_i > r_j$ و یا $r_i > l_j$ باشد. برنامه‌ای بنویسید که با گرفتن قدرت دست‌های ورزشکاران، ورزشکارانی را که شانس کسب مدال طلای مسابقات را دارند، پیدا کند. # ورودی در خط اول ورودی عدد طبیعی $n$، تعداد ورزشکاران، آمده است. در هر یک از $n$ خط بعدی، قدرت دست‌های ورزشکاران آمده است. در خط $i$ از این خطوط، به ترتیب دو عدد طبیعی $r_i$ و $l_i$ آمده است که نشان‌دهنده‌ی قدرت دست راست و دست چپ ورزشکار $i$ است. تضمین می‌شود تمامی $l_i$ها و $r_i$ها متمایز هستند. $$1\leq n \leq 200\ 000$$ $$1\leq l_i, r_i\leq 2 \times n$$ # خروجی در تنها خط خروجی یک رشته‌ی $n$ حرفی از `0` و `1` چاپ کنید که `1` بودن حرف $i$ام این رشته نشان‌دهنده‌ی این است که ورزشکار $i$ام شانس قهرمانی دارد. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۱۲ | $n\le 20$ | | ۲ | ۱۶ | $n\le 200$ | | ۳ | ۲۸ | $n \le 2\ 000$ | | ۴ | ۴۴ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 2 1 2 3 4 ``` ## خروجی نمونه ۱ ``` 01 ``` ## ورودی نمونه ۲ ``` 4 1 8 6 7 5 4 3 2 ``` ## خروجی نمونه ۲ ``` 1111 ```

+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دو گراف $n$ راسی به شما داده شده است که راس‌های آن‌ها از $1$ تا $n$ شماره‌گذاری شده اند. در هر مرحله می‌توان یال‌های متصل به یک راس در گراف اول را یک بار به صورت ساعتگرد یا پادساعتگرد چرخاند. عمل چرخاندن یک راس مانند $v$ به این شکل انجام می‌شود که در ازای هر یال از $v$ به $u$ در گراف، یک یال جدید از $v$ به $next_v(u)$ قرار داده می‌شود و تمامی یال‌های قدیمی راس $v$ پاک می‌شود. برای حرکت چرخاندن ساعتگرد، تابع $next$ به شکل زیر تعریف می‌شود: $$ next_{v}(u)= \begin{cases} u \oplus 1, & u \oplus 1 \ne v \\ u \oplus 2, & u \oplus 1 = v \end{cases} $$ برای چرخاندن پادساعتگرد نیز تابع $next$ به طور مشابهی ساخته می‌شود: $$ next_{v}(u)= \begin{cases} u \oplus -1, & u \oplus -1 \ne v \\ u \oplus -2, & u \oplus -1 = v \end{cases} $$ منظور از عملگر $\oplus$ جمع دوری است که به شکل زیر تعریف می شود: $$ i \oplus j = \begin{cases} i + j \mod n, & i + j \mod n \ne 0\\ n, & i + j \mod n = 0 \end{cases} $$ هدف تبدیل گراف اول به گراف دوم در تعدادی حرکت است. آیا این کار امکان پذیر است؟ # ورودی در خط اول ورودی عدد طبیعی $n$، تعداد راس‌های گراف‌ها آمده است. در $n$ خط بعدی از ورودی در هر خط یک رشته‌ی $n$ حرفی از 0 و 1 آمده است که ماتریس مجاورت گراف اول را نشان می‌دهد و 1 بودن حرف $j$ام خط $i$ام وجود یک یال از $i$ به $j$ در گراف اول را نشان می‌دهد. در $n$ خط بعدی به حالت مشابه ماتریس مجاورت گراف دوم آمده است. تضمین می‌شود ماتریس‌های ورودی متقارن هستند و درایه‌های روی قطرشان برابر با صفر است. $$1 \le n \le 50$$ # خروجی در صورتی که نمی‌توان گراف اول را به گراف دوم تبدیل کرد در یک خط عبارت `impossible` را چاپ کنید. در غیر این‌صورت ابتدا تعداد حرکات لازم برای تبدیل گراف اول به گراف دوم را چاپ کنید و در خطوط بعدی حرکات را به شکل `- v` یا `+ v` چاپ کنید. `- v` یک چرخاندن ساعتگرد بر روی راس $v$ و `+ v` یک چرخاندن پادساعتگرد بر روی راس $v$ را نشان می‌دهد. دقت کنید لزومی ندارد که تعداد حرکات مینیمم باشد و جواب شما اگر کمتر از $300\ 000$ حرکت داشته باشد قابل قبول است. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۱۱ | $n \le 7$ | | ۲ | ۱۱ | تضمین می‌شود درجه هر راس در گراف‌ها دقیقاً یک است. | | ۳ | ۲۲ | تضمین می‌شود گراف‌ها درخت هستند. | | ۴ | ۵۶ | بدون محدودیت اضافی | # مثال ## ورودی نمونه ۱ ``` 4 0101 1000 0001 1010 0011 0001 1000 1100 ``` ## خروجی نمونه ۱ ``` 10 + 2 + 2 - 3 + 2 + 4 - 1 + 4 + 1 - 4 - 4 ```