CF2193H.Remove the Grail Tree

The Great Grail Tree has stood in the kingdom for $315$ years. It takes up a lot of space, so King Ila decided to get rid of it as soon as possible. The tree itself is an acyclic, connected, undirected graph with $n$ vertices, each having its own value $a_v$. The tree can be removed in the following way:

• Let $S_v$ be the sum of the values of all remaining neighbors of $v$. If $v$ has no remaining neighbors, then $S_v$ is $0$. Choose a vertex $v$ such that $a_v$ and $S_v$ differ in parity (i.e., either $a_v$ is even and $S_v$ is odd, or $a_v$ is odd and $S_v$ is even). If there are no such vertices, stop the process.
• Remove vertex $v$ and all edges connected to it from the tree.

Your task is to determine whether there exists a sequence of removals that will lead to the complete removal of the Grail Tree (i.e., no vertices will remain in the tree). If such a sequence exists, output the sequence of $n$ vertices in the order of their removal. If there are multiple answers, output any of them.

伟大的圣杯树已在王国中矗立了 $315$ 年。它占据大量空间，因此伊拉国王决定尽快将其彻底移除。该树本身是一棵具有 $n$ 个顶点的无环、连通、无向图，每个顶点 $v$ 均具有一个权值 $a_v$。树可通过如下方式被移除：

• 设 $S_v$ 为顶点 $v$ 当前所有剩余邻接顶点的权值之和；若 $v$ 没有剩余邻接顶点，则 $S_v = 0$。选择一个顶点 $v$，使得 $a_v$ 与 $S_v$ 的奇偶性不同（即：$a_v$ 为偶数而 $S_v$ 为奇数，或 $a_v$ 为奇数而 $S_v$ 为偶数）。若不存在满足条件的顶点，则停止该过程。
• 将顶点 $v$ 及其所有关联边从树中移除。

你的任务是判断是否存在一种移除序列，使得圣杯树被完全移除（即：树中不再剩余任何顶点）。若存在这样的序列，请输出一个长度为 $n$ 的顶点序列，表示各顶点被移除的顺序；若存在多个可行答案，输出任意一个即可。

Each test consists of several test case. The first line contains one integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line contains the number $n$ ($1\le n\le 2\cdot 10^5$) — the number of vertices in the Grail Tree.

The second line describes the array $a$ ($1\le a_i\le 10^9$) — the values of the vertices in the tree.

Next, there are $n - 1$ lines, each containing 2 numbers $v$ and $u$ ($1\le v, u\le n, v\neq u$), indicating that vertices $v$ and $u$ are connected by an edge in the tree.

It is guaranteed that the sum of $n$ across all test cases does not exceed $2\cdot 10^5$.

每个测试包含若干测试用例。第一行包含一个整数 $t$（$1\le t\le 10^4$）—— 测试用例的数量。随后是各测试用例的描述。

第一行包含一个整数 $n$（$1\le n\le 2\cdot 10^5$）—— 圣杯树（Grail Tree）中的顶点数量。

第二行描述数组 $a$（$1\le a_i\le 10^9$）—— 树中各顶点的权值。

接下来有 $n - 1$ 行，每行包含两个数 $v$ 和 $u$（$1\le v, u\le n,\, v\neq u$），表示顶点 $v$ 和 $u$ 在树中由一条边相连。

保证所有测试用例中 $n$ 的总和不超过 $2\cdot 10^5$。

For each test case, output "YES" if it is possible to completely remove the Grail Tree. Otherwise, output "NO". If the answer is "YES", output any sequence of removals.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

对于每个测试用例，如果能够完全移除圣杯树，则输出 “YES”；否则输出 “NO”。若答案为 “YES”，则还需输出任意一种移除序列。

你可以以任意大小写形式输出每个字母（小写或大写）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均被视为有效的肯定回答。