题目描述

$N$ 頂点からなる木があり、頂点には $1$ から $N$ の番号がついています。 また、$N-1$ 本の辺の内、$i$ 番目の辺は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

今、各頂点 $i$ には $A_i$ 個の石が置いてあります。 高橋君と青木君はこの木を使ってゲームをすることにしました。

まず、高橋君が一つの頂点を選び、そこに駒を置きます。 その後、高橋君から始めて以下の操作を交互に繰り返します。

• 今、駒がおいてある頂点から石を一つ取り除く。
• その後、その頂点に隣接する頂点を一つ選び、そこに駒を動かす。

駒が置いてある頂点に石がなく、操作を行えない人が負けです。 高橋君がこのゲームに勝つために、最初に駒を置くことができる頂点をすべて求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $A_2$ … $A_N$ $a_1$ $b_1$ : $a_{N-1}$ $b_{N-1}$

输出格式

高橋君が最初に駒を置いて勝つことができる頂点の番号を昇順に一行に出力せよ。

题目大意

Description

有一棵 $n$ 个节点的树，第 $i$ 条边连接 $a_i,b_i$，每个节点 $i$ 上有 $A_i$ 个石子，高桥君和青木君将在树上玩游戏

首先，高桥君会选一个节点并在上面放一个棋子，然后从高桥君开始，他们轮流执行以下操作：

从当前棋子占据的点上移除一个石子 将棋子移动到相邻节点 如果轮到一个人执行操作时棋子占据的点上没有石子，那么他就输了

请你找出所有的点 $v$，使得如果高桥君在游戏开始时把棋子放到 $v$ 上，他可以赢

Input

第一行一个整数 $n$

第二行 $n$ 个整数 $A_{1..n}$

接下来行每行两个整数 $a_i,b_i$ 表示一条边

Output

以编号递增的顺序在一行中输出所有满足条件的点

3
1 2 3
1 2
2 3

2

5
5 4 1 2 3
1 2
1 3
2 4
2 5

1 2

3
1 1 1
1 2
2 3

提示

制約

• $2\ ≦\ N\ ≦\ 3000$
• $1\ ≦\ a_i,b_i\ ≦\ N$
• $0\ ≦\ A_i\ ≦\ 10^9$
• 与えられるグラフは木である。

Sample Explanation 1

高橋君が頂点 $2$ に駒を置いたとき、例えば以下のようにゲームが進みます。 - 高橋君が駒を頂点 $1$ に動かす。このとき、各頂点にある石の個数は $(1,1,3)$ である。 - 青木君が駒を頂点 $2$ に動かす。このとき、各頂点にある石の個数は $(0,1,3)$ である。 - 高橋君が駒を頂点 $1$ に動かす。このとき、各頂点にある石の個数は $(0,0,3)$ である。 - 青木君が石を取れないため、高橋君の勝ちとなる。

Sample Explanation 3

題意を満たす頂点が存在しない場合があることに注意してください。