Masala E

Algoritm City da \(n\) ta chorraha va ular orasida \(m\) ta ikki tomonlama yo‘l bor.

Har bir chorraha \(v\) uchun shahar qoidasi berilgan:
 

• \(r[v]=0\) bo‘lsa — \(v\) dan chiqadigan yo‘naltirilgan yo‘llar soni juft bo‘lishi kerak.
• \(r[v]=1\) bo‘lsa — \(v\) dan chiqadigan yo‘naltirilgan yo‘llar soni toq bo‘lishi kerak.

Sizning vazifangiz: har bir ikki tomonlama yo‘lga yo‘nalish bering (ya’ni \(u \to v\) yoki \(v \to u\)).

Agar barcha chorrahalar uchun talablarga mos yo‘nalish berish imkonsiz bo‘lsa, \(-1\) chiqaring.
Aks holda, yo‘llarning kiritilgan tartibida ularning yo‘nalishini chiqaring.

Agar bir nechta yechim mavjud bo‘lsa, istalgan bittasini chiqarsangiz bo‘ladi.
 

Birinchi qatorda \(n\) va \(m\) beriladi.

Ikkinchi qatorda \(n\) ta son \(r_1, r_2, \dots, r_n\) \(\big(r_i \in \{0,1\}\big)\) beriladi.

Keyingi \(m\) qatorda \(u_i\) va \(v_i\) — \(i\)-yo‘lning ikki uchi (ya’ni qaysi ikkita chorrahani bog‘laydi) beriladi.

Chegaralar:

\(1 \le n \le 2 \cdot 10^5\)

\(1 \le m \le 2 \cdot 10^5\)

\(1 \le u_i, v_i \le n,\; u_i \ne v_i\)

Bir xil ikki chorraha orasida bir nechta yo‘l bo‘lishi mumkin (parallel yo‘llar bo‘lishi mumkin).

O‘z-o‘ziga yo‘l yo‘q.

Agar yechim bo'lmasa: \(-1\)

Aks holda \(m\) qatorda (yo'llar kiritilgan tartibda) \(a_i\) \(b_i\) chiqaring — bu \(i\)-yo'l \(a_i \to b_i\) yo'nalishda qo'yilganini bildiradi.