• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

علی برای افزایش روحیه تیم ترب تصمیم گرفته آن‌ها را به اسکیپ روم ببرد... آن‌ها باید سوال زیر را حل کنند تا وارد مرحله بعد شوند... به آن‌ها کمک کنید تا این گردش برایشان جذاب شود

یک گراف ساده مانند $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