E. Yet Another Y Flip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ nodes.Node $$$1$$$ is the root node.The value of each node is either $$$0$$$ or $$$1$$$.

Define a Y as an node set which contains $$$4$$$ nodes.The descriptions of the $$$4$$$ nodes are as follows:

  1. A node(note it as $$$x$$$) with at least two child nodes;
  2. The parent node of $$$x$$$;
  3. Any two child nodes of $$$x$$$.

You can do the following operation any number of times:choose a Y in the tree,flip each value of nodes in it.

Flip means:if the value is $$$0$$$ change it to $$$1$$$,otherwise change it to $$$0$$$.

Find if you can change the values of all nodes to $$$0$$$.

Input

The first line of input will contain a single integer $$$t(1 \leq t \leq 10^5)$$$, denoting the number of test cases.

For each test case:

The first line of each test case contains an integer $$$n(4 \leq n \leq 10^5)$$$.

The next line contains $$$n$$$ integers $$$a_1,a_2,...,a_n(0 \leq a_i \leq 1)$$$— the value of node from $$$1$$$ to $$$n$$$.

The next $$$n-1$$$ line of each test case contains two integers:$$$u,v(1 \leq u,v \leq n)$$$.It means there's an edge between node $$$u$$$ and $$$v$$$.

The sum of $$$n$$$ over all test cases won't exceed $$$10^5$$$.

Output

For each test case, output on a new line — if you can change the values of all nodes to $$$0$$$,output $$$YES$$$.Otherwise,output $$$NO$$$.

Example
Input
8
4
0 0 0 0
1 2
1 3
2 4
4
1 1 1 0
1 2
1 3
2 4
7
1 0 0 1 0 0 0
1 2
2 3
2 4
3 5
3 6
3 7
7
0 1 1 0 0 0 0
1 2
1 3
1 4
2 5
3 6
4 7
10
0 0 0 0 0 0 0 1 0 1
1 4
2 4
3 2
4 10
5 2
6 3
7 3
8 2
9 3
10
1 0 0 1 0 0 1 0 0 1
1 2
2 4
3 2
4 10
5 3
6 4
7 4
8 3
9 3
10
1 1 0 0 1 0 0 0 1 0
1 4
2 10
3 4
4 2
5 2
6 5
7 3
8 4
9 2
12
1 0 1 0 0 0 0 0 0 0 0 0
1 2
2 3
2 4
4 5
4 6
5 7
5 8
5 9
6 10
6 11
6 12
Output
YES
NO
YES
NO
NO
YES
YES
YES
Note

Test case $$$1$$$:

Since the values of all nodes are already $$$0$$$,you don't need to do any operations.

Test case $$$2$$$:

Since you can not do any operations at all and $$$a_1=a_2=a_3=1$$$,you can not change the values of all nodes to $$$0$$$.

Test case $$$3$$$:

  1. Flip node $$$2,1,3,4$$$
  2. Flip node $$$3,2,5,6$$$
  3. Flip node $$$3,2,5,7$$$
  4. Flip node $$$3,2,6,7$$$