大圣杯树在王国中已经矗立了$$$315$$$年。它占用了很大的空间,所以国王伊拉决定尽快摆脱它。树本身是一个非循环、连通、无向图,具有 $$$n$$$ 个顶点,每个顶点都有自己的值 $$$a_v$$$。可以通过以下方式删除树:
- 令 $$$S_v$$$ 为 $$$v$$$ 的所有剩余邻居的值之和。如果 $$$v$$$ 没有剩余的邻居,则 $$$S_v$$$ 是 $$$0$$$。选择一个顶点 $$$v$$$,使得 $$$a_v$$$ 和 $$$S_v$$$ 奇偶性不同(即,$$$a_v$$$ 是偶数,$$$S_v$$$ 是奇数,或者 $$$a_v$$$ 是奇数,$$$S_v$$$ 是偶数)。如果没有这样的顶点,则停止该过程。
- 从树中删除顶点 $$$v$$$ 以及与其连接的所有边。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
第一行包含数字 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — 圣杯树中的顶点数。
第二行描述数组 $$$a$$$ ($$$1\le a_i\le 10^9$$$) — 树中顶点的值。
接下来有 $$$n - 1$$$ 行,每行包含 2 个数字 $$$v$$$ 和 $$$u$$$ ($$$1\le v, u\le n, v\neq u$$$),表示顶点 $$$v$$$ 和 $$$u$$$ 通过树中的边连接。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,如果可以完全删除圣杯树,则输出“YES”。否则,输出“NO”。如果答案为“是”,则输出任何移除序列。
您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。
示例
输入复制
531 2 41 22 343 4 2 11 22 33 469 6 5 1 7 41 22 32 43 54 652 1 1 1 22 13 22 45 451 5 3 7 91 22 33 44 5
输出复制
NOYES2 3 1 4NOYES1 5 2 3 4YES2 4 1 5 3