Alice and Bob are playing a game on a tree of n nodes. Each node is either black or white initially.

They take turns to do the following operation:

• Choose a white node v from the current tree;
• Color all white nodes on Path(1, v) to black.

The player who takes the last turn wins.

Now Alice takes the first turn. Help her find out if she can win when they both use optimal strategy.

Input

The first line of input contains a integer n representing the number of nodes in the tree. 1<=n<=100000

The second line contains n integers c1, c2 ,.. cn. 0<=ci<=1.
ci=0 means the ith node is white initially and ci=1 means black.

Next n-1 lines describes n-1 edges in the tree. Each line contains two integers u and v, means there is a edge connecting u and v. 

Output

If Alice can't win print -1.

Otherwise determine all the nodes she can choose in the first turn in order to win. Print them in ascending order.

Example

Input #1:
8
1 1 0 1 0 0 1 0
1 2
1 3
2 6
3 4
3 5
5 7
7 8 

Output #1:
5

Input #2:
20
1 1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 0 0 0 0
1 2
2 3
2 4
1 5
1 6
5 7
5 8
2 9
8 10
1 11
1 12
9 13
6 14
14 15
7 16
11 17
2 18
7 19
12 20 

Output #2
8
11
12