B. Computer Operations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$N$$$ computers; each one is either turned on or off.

The computers are connected to each other by $$$N - 1$$$ cables; the connections form a tree$$$^\dagger$$$.

You can do the following operation:

  • Switch the state of one computer and all the computers that are directly connected to it by a cable.

Determine whether it is possible to make all the computers turned on.

$$$\dagger$$$  A tree is a connected undirected graph with $$$N$$$ nodes and $$$N - 1$$$ edges.

Input

The first line of the input contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — the number of computers.

The second line of each testcase consists of $$$N$$$ space-separated integers $$$A_1, A_2, \dots, A_N$$$ ($$$A_i \in \{0, 1\}$$$) — the initial state of each computer. If $$$A_i = 0$$$, then the $$$i$$$-th computer is turned off, and if $$$A_i = 1$$$, then the $$$i$$$-th computer is turned on.

Each of the following $$$N - 1$$$ lines consists of two space-separated integers $$$U$$$ and $$$V$$$ ($$$1 \le U, V \le N$$$, $$$U \neq V$$$) — a cable between the computers $$$U$$$ and $$$V$$$ exists.

It is guaranteed that the sum of $$$N$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

Output

Output $$$T$$$ lines, each containing a single string "Yes" (without quotes) if it is possible to make all the computers turned on, or "No" (without quotes) otherwise.

You may print each letter of "Yes" and "No" in any case (for example, "yEs", "yes", "No", "NO" will all be accepted).

Example
Input
3
5
0 1 0 1 1 
1 2
1 3
3 4
3 5
8
1 1 0 0 0 0 0 1 
2 1
3 2
4 3
5 4
6 5
7 6
8 7
4
1 0 0 0 
1 2
2 3
3 4
Output
YES
NO
YES