题目描述

有一棵 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。其中第 $i$ 条 $(1 \le i \le N - 1)$ 边连接顶点 $a_i$ 和 $b_i$。

当前，在第 $i$ 个顶点上放置了 $A_i$ 个石头。高桥和青木将在这棵树上进行游戏。

首先，高桥会选择一个顶点并在其上放置一个棋子。然后，从高桥开始，他们将交替执行以下操作：

• 从当前棋子所在的顶点移除一个石头。
• 然后，将棋子移动到与当前棋子所在的顶点相邻的一个顶点上。

当一个玩家在棋子所占据的顶点上没有石头，因此无法执行操作时，他将输掉游戏。请找出所有满足高桥可以在开始时把棋子放在 $v$ 上并赢得游戏的顶点 $v$。

约束条件

• $2 ≤ N ≤ 3000$
• $1 ≤ a_i, b_i ≤ N$
• $0 ≤ A_i ≤ 10^9$
• 给定图是一棵树。

输入

从标准输入读取的输入数据格式如下：

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

输出

按照升序，逐行输出高桥可以在开始时把棋子放在的顶点 $v$ 的索引。

示例 1

3
1 2 3
1 2
2 3

输出 1

2

当高桥把棋子放在顶点 $2$ 上时，游戏可能的进展如下：

• 高桥将棋子移动到顶点 $1$。各顶点上的石头数目变为：$(1,1,3)$。
• 青木将棋子移动到顶点 $2$。各顶点上的石头数目变为：$(0,1,3)$。
• 高桥将棋子移动到顶点 $1$。各顶点上的石头数目变为：$(0,0,3)$。
• 青木无法从顶点上取走石头，因此高桥获胜。

示例 2

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

输出 2

1 2

示例 3

3
1 1 1
1 2
2 3

输出 3

注意：正确的输出可能为空行。