Tô đen cả cây

Cho một cây gồm $n$ đỉnh, đánh số từ $1$ đến $n$. Mỗi đỉnh được tô một trong hai màu: đen hoặc hồng.

Một quân cờ xuất phát tại đỉnh $1$. Ở mỗi bước, quân cờ di chuyển từ đỉnh hiện tại sang một đỉnh kề với nó và đổi màu của đỉnh vừa đi tới: đỉnh hồng trở thành đen, đỉnh đen trở thành hồng. Riêng đỉnh $1$ không bị đổi màu ở thời điểm xuất phát, nó chỉ đổi màu nếu quân cờ đi tới nó ở một bước sau đó.

Hãy tìm một hành trình sao cho sau khi quân cờ dừng lại, tất cả $n$ đỉnh đều có màu đen. Hành trình là dãy các đỉnh mà quân cờ đi qua theo thứ tự, bắt đầu bằng đỉnh $1$, trong đó hai đỉnh liên tiếp bất kỳ phải kề nhau trên cây. Quân cờ được phép đi qua cùng một đỉnh nhiều lần và có thể dừng lại ở đỉnh bất kỳ.

Dữ liệu đảm bảo luôn tồn tại đáp án. Nếu có nhiều hành trình hợp lệ, in ra một hành trình bất kỳ, miễn là số đỉnh của hành trình không vượt quá ${10}^7$.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số đỉnh của cây.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa số nguyên $c_i$ mô tả màu của đỉnh $i$: $c_i=1$ nếu đỉnh $i$ màu đen, $c_i=-1$ nếu đỉnh $i$ màu hồng.
• $n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ mô tả một cạnh nối đỉnh $u$ và đỉnh $v$.

Dữ liệu ra

In ra dãy chỉ số các đỉnh của hành trình theo đúng thứ tự đi qua, cách nhau bởi dấu cách. Nếu tất cả các đỉnh ban đầu đã có màu đen, bạn có thể in ra $1$ (hành trình chỉ gồm đỉnh xuất phát).

Ràng buộc

• $2\le n\le 2·{10}^5$
• $c_i\in \{-1,1\}$
• $1\le u,v\le n$, các cạnh tạo thành một cây.
• Hành trình in ra có không quá ${10}^7$ đỉnh.

Ví dụ