E. Enter the Museum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Petya wants to visit the only museum in his city.

The museum contains $$$n$$$ rooms connected by $$$n - 1$$$ corridors, with the entrance located in room number $$$1$$$. It is possible to reach any other room from there by moving through the corridors.

Since Petya likes to plan everything in advance, he wants to plan his route through the museum. He will start in room number $$$1$$$, and each time he passes through a corridor, he will study exactly one exhibit in the room he arrives at. Petya doesn't want to waste time, so he wants to finish his path back in room $$$1$$$ without studying the same exhibit twice. Additionally, he won't start studying exhibits until he has moved through at least one corridor.

Help Petya create a route that allows him to study all the exhibits, or tell him that it is impossible.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 10^5$$$): the number of rooms in the museum.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^5$$$): the number of exhibits in the first, second, $$$\ldots$$$, and last room of the museum.

The $$$i$$$-th of the following $$$n - 1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), indicating that museum rooms $$$u_i$$$ and $$$v_i$$$ are directly connected by a corridor.

It is guaranteed that the total number of exhibits is at most $$$2 \cdot 10^5$$$. It is guaranteed that all rooms are reachable from room $$$1$$$ using only the described corridors.

Output

If it is possible to create a route that allows Petya to study all the exhibits, output $$$1 + \sum_{i = 1}^{n}{a_i}$$$ numbers: the order of visiting the museum rooms, starting and ending in room number $$$1$$$. Otherwise, if it is not possible, output a single integer $$$0$$$.

If there are multiple solutions, print any of them.

Examples
Input
4
1 1 2 4
1 4
2 4
3 4
Output
1 4 2 4 3 4 3 4 1
Input
2
3 6
1 2
Output
0