题目描述

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

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

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

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

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

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

输入格式

第一行输入一个整数 $t$（$1 \le t \le 10^5$）—— 测试用例的数量。
每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 4 \cdot 10^5$）—— 树中节点的数量。
第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$（$1 \le w_i \le n$）—— 每个节点的权值。
接下来的 $n-1$ 行包含树的边。第 $i$ 行包含两个整数 $u_i, v_i$（$1 \le u_i, v_i \le n$，$u_i \neq v_i$）—— 连接 $u_i$ 和 $v_i$ 的边。输入保证这些边构成一棵树。
保证所有测试用例的 $n$ 之和不超过 $4 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行。
如果 Cirno 获胜，输出若干个整数。第一个整数 $k$ 表示她第一回合可能选择的节点数量，之后按递增顺序输出这 $k$ 个节点。
否则，输出 $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 2 4
0
1 2
1 2
5 3 4 6 7 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$。