Cây XOR

Cho một cây có $n$ đỉnh, đánh số từ $1$ đến $n$, gốc tại đỉnh $1$. Mỗi đỉnh $i$ có một giá trị ban đầu $ini{t}_i\in \{0,1\}$.

Một thao tác được định nghĩa như sau: chọn một đỉnh $x$. Khi đó:

• Giá trị của $x$ bị đảo ($0\leftrightarrow 1$).
• Các con (cách $x$ một cạnh) của $x$ giữ nguyên.
• Các cháu (cách $x$ hai cạnh) bị đảo.
• Cứ tiếp tục như vậy: ở khoảng cách chẵn so với $x$ thì đảo, ở khoảng cách lẻ thì giữ nguyên.

Hãy đưa giá trị của mỗi đỉnh $i$ về đúng $goa{l}_i\in \{0,1\}$ bằng số thao tác ít nhất.

Dữ liệu vào

• Dòng đầu: số nguyên $n$.
• $n-1$ dòng tiếp theo: hai số $u_i,v_i$ — một cạnh của cây.
• Dòng tiếp theo: $n$ số $ini{t}_1,ini{t}_2,\dots ,ini{t}_n$.
• Dòng cuối: $n$ số $goa{l}_1,goa{l}_2,\dots ,goa{l}_n$.

Dữ liệu ra

• Dòng đầu: số nguyên $cnt$ — số thao tác tối thiểu.
• $cnt$ dòng tiếp theo: mỗi dòng một số $x_i$ — đỉnh được chọn ở thao tác thứ $i$.

Nếu có nhiều phương án tối ưu, in ra phương án bất kỳ. Thứ tự thực hiện các thao tác không ảnh hưởng đến kết quả cuối cùng.

Ràng buộc

• $1\le n\le {10}^5$
• $1\le u_i,v_i\le n$, $u_i\ne v_i$
• $ini{t}_i,goa{l}_i\in \{0,1\}$
• Các cạnh tạo thành một cây có gốc tại đỉnh $1$.

Ví dụ