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

Điểm: 8,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

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á $4 n$ .

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} \neq 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 \leq k \leq 4 n$ ).
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 \leq n \leq 10^{5}$
$0 \leq m \leq 10^{5}$
$1 \leq u_{i}, v_{i} \leq n$ , $u_{i} \neq v_{i}$
$0 \leq x_{i} \leq 1$
Đồ thị không có khuyên và không có cạnh kép.

Ví dụ

Input	Output	Giải thích
3 2 1 2 2 3 1 1 1	7 3 2 1 2 3 2 3	Đỉnh $1$ xuất hiện $1$ lần (lẻ), đỉnh $2$ xuất hiện $3$ lần (lẻ), đỉnh $3$ xuất hiện $3$ lần (lẻ). Phù hợp với $x = (1, 1, 1)$ . Mọi đường đi khác thỏa ràng buộc (ví dụ "1 2 3") đều được chấp nhận.
5 7 1 2 1 3 1 4 1 5 3 4 3 5 4 5 0 1 0 1 0	12 4 1 2 1 3 5 3 5 3 1 3 1	Đỉnh $2$ và $4$ xuất hiện số lần lẻ; các đỉnh còn lại $1, 3, 5$ xuất hiện số chẵn lần.
2 0 0 0	0	Tất cả $x_{i} = 0$ , đường đi rỗng là hợp lệ.

Bình luận

Không có bình luận tại thời điểm này.