题目描述

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。此外，第 $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}$

输出格式

请按升序输出所有高桥君可以选择并保证获胜的初始顶点编号，输出在一行内，用空格分隔。

样例 1

输入

3
1 2 3
1 2
2 3

输出

2

样例 2

输入

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

输出

1 2

样例 3

输入

3
1 1 1
1 2
2 3

输出

说明/提示

限制条件

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

样例解释 1

当高桥君将棋子放在顶点 $2$ 时，游戏可能如下进行：

• 高桥君将棋子移动到顶点 $1$。此时各顶点的石子数为 $(1,1,3)$。
• 青木君将棋子移动到顶点 $2$。此时各顶点的石子数为 $(0,1,3)$。
• 高桥君将棋子移动到顶点 $1$。此时各顶点的石子数为 $(0,0,3)$。
• 青木君无法取石子，因此高桥君获胜。

样例解释 3

请注意，可能不存在满足条件的顶点。

由 ChatGPT 4.1 翻译