Đường đi theo tính chẵn lẻ

Cho một đồ thị vô hướng $n$ đỉnh, $m$ cạnh, không có khuyên và không có cạnh kép. Mỗi đỉnh $i$ được gán một giá trị $x_i\in \{0,1\}$ — chính là tính chẵn lẻ của số lần đỉnh đó phải xuất hiện trong đường đi.

Bạn cần tìm một đường đi (có thể rỗng) thỏa mãn:

• Hai đỉnh liên tiếp trên đường đi phải có cạnh nối trực tiếp trong đồ thị.
• Mỗi đỉnh $i$ xuất hiện trên đường đi đúng số lần có cùng tính chẵn lẻ với $x_i$ (nếu $x_i=0$ thì xuất hiện số lần chẵn, kể cả $0$ lần; nếu $x_i=1$ thì xuất hiện số lần lẻ).
• Tổng số đỉnh trên đường đi (đếm cả lặp lại) không vượt quá $4n$.

Một đỉnh có thể được ghé thăm nhiều lần. Đường đi có thể bắt đầu và kết thúc ở bất kỳ đỉnh nào, hoặc rỗng (không có đỉnh nào).

Nếu không tồn tại đường đi như vậy, in ra $-1$.

Dữ liệu vào

• Dòng đầu: hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u_i,v_i$ — một cạnh giữa hai đỉnh $u_i$ và $v_i$ ($u_i\ne v_i$).
• Dòng cuối: $n$ số nguyên $x_1,x_2,\dots ,x_n$, mỗi số là $0$ hoặc $1$.

Dữ liệu ra

Nếu không tồn tại đường đi, in ra một số $-1$.

Ngược lại, in ra hai dòng:

• Dòng đầu: số lượng đỉnh $k$ trên đường đi ($0\le k\le 4n$).
• Dòng thứ hai: $k$ số nguyên — danh sách các đỉnh theo thứ tự xuất hiện trên đường đi. Nếu $k=0$ thì có thể bỏ trống dòng này.

Nếu có nhiều đáp án, in ra bất kỳ.

Ràng buộc

• $2\le n\le {10}^5$
• $0\le m\le {10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $0\le x_i\le 1$
• Đồ thị không có khuyên và không có cạnh kép.

Ví dụ