+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- *علی برای افزایش روحیه تیم ترب تصمیم گرفته آن‌ها را به اسکیپ روم ببرد... آن‌ها باید سوال زیر را حل کنند تا وارد مرحله بعد شوند... به آن‌ها کمک کنید تا این گردش برایشان جذاب شود* یک گراف ساده مانند $G$ با $n$ راس با شماره‌های ۱ تا $n$ و $m$ یال دو طرفه داریم. بین هر دو راس حداکثر یک یال وجود دارد. هر یال دو راس مختلف را به هم وصل می‌کند. توجه کنید لزوماً این گراف همبند نیست! هر راس از این گراف در ابتدا با یکی از دو رنگ سیاه و سفید رنگ آمیزی شده است. در هر عملیات می‌توانیم یک زیر مجموعه از رئوس مانند $S$، انتخاب کنیم و رنگ هر راس در مجموعه $S$ و همه رئوسی که به حداقل یک راس از $S$ یال دارند را عوض کنیم. (رنگ سفید را به سیاه و رنگ سیاه را به سفید) می‌خواهیم با حداکثر $n + 1$ عملیات کل رئوس گراف را سفید کنیم. اگر چنین کاری ممکن است یک روش برای انجام این کار ارائه دهید در غیر اینصورت بگویید این کار ممکن نیست. # ورودی در خط اول ورودی دو عدد صحیح $n$ و $m$ با فاصله از هم آمده است. $$0 \le n \le 1500$$$$ 0 \le m \le \frac{n(n - 1)}{2}$$ در سطر بعدی یک رشته از $0$ و $1$ به طول $n$ آمده است که اگر عدد $i$ام آن $0$ باشد یعنی راس شماره $i$ سفید و اگر $1$ باشد یعنی رنگ راس شماره $i$ سیاه است. در $m$ سطر بعدی هر کدوم دو عدد $u$ و $v$ آمده است. که نشان دهنده یال‌های گراف است. $$ 1 \le u \neq v \le n$$ # خروجی در صورت امکان پذیر بودن در سطر اول $k$ که تعداد مراحلی که نیاز دارید تا رنگ همه رئوس را سفید کنید چاپ کنید. $$0 \le k \le n + 1$$ در $k$ سطر بعدی در هر سطر یک رشته از $0$ و $1$ چاپ کنید که عدد $i$ام آن $1$ است اگر راس شماره $i$ در مرحله $i$ام در مجموعه $S$ باشد و در غیر اینصورت $0$ خواهد بود. در صورت امکان پذیر نبودن در تنها سطر خروجی `-1` را چاپ کنید. # مثال ## ورودی نمونه ۱ ``` 4 3 0110 1 2 2 3 3 4 ``` ## خروجی نمونه ۱ ``` 3 0100 0010 1001 ``` ## ورودی نمونه ۲ ``` 3 3 110 1 2 2 3 3 1 ``` ## خروجی نمونه ۲ ``` -1 ``` # قسمت آموزشی در این قسمت راهنمایی‌های سوال، به مرور اضافه می‌شود. مشکلات‌تان در راستای حل سوال را می‌توانید از بخش ["سوال بپرسید"](https://quera.ir/contest/clarification/19378/) مطرح کنید. <details class="blue"> <summary>راهنمایی ۱</summary> اول بیاییم یک شرط برای `-1` شدن جواب پیدا کنیم. فرض کنید دو تا راس $u$ و $v$ که به هم وصل هستند و مجموعه همسایه های یکسانی دارند، رنگشان فرق دارد. این‌جوری هیچ مجموعه‌ای که دقیقا یکی از این دو راس را شامل شود، نداریم. پس جواب برابر `-1` است. </details> <details class="blue"> <summary>راهنمایی ۲</summary> ابتدا به ازای هر $u$ و $v$ که با هم همسایه‌اند و مجموعه همسایه‌هایشان برابر است، یکی را حذف کنید چون رنگ این دو همیشه برابر است و در انتها هر دو سفید می‌شوند. حال راس‌های گراف را بر حسب درجه مرتب کنید. فرض کنید برای هر راس $v$ می‌توانیم با تعدادی عملیات رنگ $v$ را عوض کنیم طوری که برای هر $u$ که $deg_v \le deg_u$ رنگ $u$ ثابت بماند. حال راس هارا به ترتیب درجه از بزرگ بررسی کنید و به هرکس که رسیدید، رنگ او را با عملیات گفته شده تغییر دهید. </details> <details class="blue"> <summary>راهنمایی ۳</summary> ادعا میکنیم عملیات گفته شده در قبل برای راس $v$ اینگونه انجام میشود: یکبار $S$ را برابر تمام ریوس غبر از $v$ قرار دهید که با $v$ مجاور نیستند. و یکبار هم $S$ را برابر با تمام ریوس قرار دهید. بدیهتا عملیات دوم رنگ تمام ریوس را تغییر میدهد پس بیایید عملیات اول را بررسی کنیم: بدیهتا هر راس غیر همسایه $v$ تغییر میکند و خود $v$ نیز تغییر نمیکند. پس فقط همسایه های $v$ میمانند. اگر راس $u$ داشتیم که $deg_u>deg_v$ رنگ $u$ تغییر میکند چون به حداقل یک راس غیر همسایه $v$ وصل است. اگر هم راس $u$ با درجه برابر $v$ داشتیم باز هم $u$ همسایه ای در $S$ دارد وگرنه مجموعه همسایه های $u$ و $v$ برابر بود. پس با عملیات اول رنگ همه به جز $v$ و تعدادی از همسایه های با درجه کمترش عوض میشوند و پس از عملیات دوم که رنگ همه عوض میشود انگار فقط رنگ $v$ و تعدادی راس با درجه کمتر عوض شده است. با این روش به ازای هر راس حداکثر 2 عملیات انجام داده ایم که یکی از انها روی تمام ریوس بوده است. چون از هر نوع عملیات فقط زوجیت تعداد دفعات ان مهم است پس در مجموع $n+1$ عملیات داریم. زمان اجرای این راه حل از $O(n^3)$ است که با `std::bitset` در زمان مطلوب اجرا میشود </details>

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