Grinch

Cerință

Se dă un graf neorientat conex cu $N$ noduri și $M$ muchii. Inițial, fiecare nod $u$ din acest graf are asociată o stare, notată cu $state_u$. Spunem că dacă $state_u$ este $1$, atunci nodul $u$ este supărat, iar dacă $state_u$ este $0$, atunci nodul $u$ este fericit. Mood Swinger-ul va alege un drum prin graf, iar, pentru fiecare nod din acest drum, își va face hazul. Când Mood Swinger-ul își face hazul în nodul $u$, acesta schimbă starea tuturor vecinilor lui $u$, dar, în mod complet surprinzător și neintuitiv, nu și a nodului $u$.

De vreme ce Mood Swinger-ul este un Grinch nenorocit, el vrea să găsească un drum în graf, astfel încât, la final, fiecare nod din graf să fie nefericit (inclusiv nodul în care se află Mood Swinger-ul).

Avem totuși, oarecum, încredere în tine că tu nu ești un Grinch și că ne poți pregăti pentru așa un necaz... Acestea fiind spuse, trebuie să găsești un drum care începe din nodul $0$ de lungime cel mult $4 \cdot N$ pe care l-ar putea parcurge Mood Swinger-ul, astfel încât starea tuturor nodurilor din graf să fie $1$ la final.

Prin drum de lungime $K$ într-un graf $G = (V, E)$, înțelegem un șir ordonat de noduri, $P$, astfel încât $(P_i, P_{i+1}) \in E$, pentru $0 \leq i \le K - 1$. Observăm că acest drum poate să repete noduri, respectiv muchii.

Date de intrare

Pe prima linie se găsesc numerele $N$ și $M$. Pe a doua linie găsim un șir binar de lungime $N$, reprezentând stările inițiale ale nodurilor. Elementele acestui șir sunt despărțite prin spații. Pe următoarele $M$ linii găsim descrierea muchiilor din graf. Fiecare dintre aceste linii conține câte două numere, $u$ și $v$, separate printr-un spațiu, indicând faptul că muchia $(u,v)$ apare în graf.

Date de ieșire

Dacă nu este posibil să găsim un astfel de drum, se va afișa $-1$. Altfel, prima linia a fișierului de ieșire va conține numărul $D$ ($0 \leq D \leq 4 \cdot N$), reprezentând lungimea drumului. Pe a doua linie se vor găsi $D$ numere din intervalul $[0, N)$, reprezentând nodurile drumului, în ordinea în care vor fi parcurse de către Mood Swinger. Amintim că drumul va începe din nodul $0$.

Dacă există mai multe soluții, se poate afișa oricare.

Restricții și precizări

• $1 \leq N \leq 500$;
• $1 \leq M \leq \frac{N \cdot (N - 1)}{2}$;
• $state_i \in \{0, 1\}$ pentru $i$ de la $0$ la $N-1$;
• Graful nu va conține muchii de forma $(u, u)$ și nu vor exista mai multe muchii între aceeași pereche de noduri;
• Pentru fiecare test, se acordă $40\%$ din punctaj dacă se determină corect dacă există sau nu soluție;
• Pentru teste în valoare de $20$ de puncte, graful descris este un arbore de tip stea.
• Pentru teste în valoare de alte $18$ puncte, $N \leq 4$;
• Pentru teste în valoare de alte $22$ de puncte, $N \leq 30$.

Exemplul 1

stdin

3 3
0 1 0
0 1
1 2
0 2

stdout

2
0 2

Explicație

Pentru graful de mai sus, putem alege drumul $(0, 2)$. După ce Mood Swinger-ul își va face hazul în nodul $0$, șirul $state$ devine $(0, 0, 1)$. După ce Mood Swinger-ul își va face hazul în nodul $2$, șirul $state$ devine $(1, 1, 1)$.

Exemplul 2

stdin

3 3
1 1 0
0 1
1 2
0 2

stdout

-1

Explicație

Pe acest caz, pare că Grinch-ul va fi cel nefericit, pentru ca nu putem găsi un drum păcătos.