题目描述

每个测试点时间限制：4 秒 每个测试点内存限制：512 兆字节

这是该问题的简单版本。两个版本的区别在于：本版本中你只需要找出 Cirno 可能选择的任意一个节点即可。只有当你解决了所有版本的问题时，你才能进行 hack。

Cirno 和 Daiyousei 在一棵有 n 个节点的树上玩游戏，树以节点 1 为根。第 i 个节点的权值为 wi。两人轮流进行操作；Cirno 先手。

在每一轮中，假设上一轮对手选择了节点 j，则当前玩家可以选择任意一个尚未被删除的节点 i，满足 wi>wj，并删除节点 i 的子树。 特别地，Cirno 在第一轮可以选择任意一个节点并删除它的子树。

无法进行操作的玩家获胜，且双方都希望获胜。找出 Cirno 在第一回合可能选择的任意一个节点，使得在双方都最优操作的情况下 Cirno 获胜。

如果从 1 到 u 的任意路径都必须经过节点 i，则认为节点 u 在节点 i 的子树中。

输入格式

第一行输入一个整数 t（1 ≤ t ≤ 10^5）—— 测试用例的数量。 每个测试用例的第一行包含一个整数 n（1 ≤ n ≤ 4·10^5）—— 树中节点的数量。 第二行包含 n 个整数 w1, w2, …, wn（1 ≤ wi ≤ n）—— 每个节点的权值。 接下来的 n-1 行包含树的边。第 i 行包含两个整数 ui, vi（1 ≤ ui, vi ≤ n，ui ≠ vi）—— 连接 ui 和 vi 的边。输入保证这些边构成一棵树。 保证所有测试用例的 n 之和不超过 4·10^5。

输出格式

对于每个测试用例，输出一行。 如果 Cirno 获胜，输出她第一回合可能选择的任意一个节点。 否则，输出 0（不带引号）。

5
4
2 2 4 3
1 2
1 3
2 4
5
1 2 3 4 5
1 2
2 3
3 4
4 5
3
1 2 3
1 2
1 3
5
3 1 3 4 5
1 2
2 3
3 4
4 5
10
1 2 3 2 4 3 3 4 4 3
1 4
4 6
7 4
6 9
6 5
7 8
1 2
2 3
2 10

2
0
2
2
10

说明

在第一个测试用例中： 若 Cirno 第一回合选择节点 1 或 3，则 Daiyousei 无法操作，Daiyousei 获胜。 若 Cirno 选择节点 2 或 4，则 Daiyousei 只能选择节点 3，之后 Cirno 无法操作，故 Cirno 获胜。 因此 Cirno 可能选择的节点为 2 和 4。 在第二个测试用例中，无论 Cirno 选择哪个节点，Daiyousei 都无法操作，故 Daiyousei 获胜。 在第三个和第四个测试用例中，Cirno 在第一回合可能选择的唯一节点是 2。 在第五个测试用例中，Cirno 在第一回合可能选择的节点为 3, 4, 6, 7 和 10。