+ محدودیت زمان: ۲ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دو گراف $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 ```

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