L. Abushogi's Escape
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Abushogi is trying to run away from the police. The city he is in can be represented as a tree consisting of $$$n$$$ intersections (nodes) and $$$n-1$$$ bidirectional roads (edges).

Abushogi is currently at the root of the tree, which is intersection $$$1$$$. He will successfully escape and be considered safe if he can reach any leaf intersection in the city.

An intersection is considered a leaf if it is connected to exactly one other intersection (and is not intersection $$$1$$$).

If the city only has $$$1$$$ intersection, intersection $$$1$$$ is considered a leaf. However, the police have deployed cops at certain intersections. Abushogi cannot pass through or land on any intersection that has a cop stationed there.

If there is a cop at intersection $$$1$$$, Abushogi is instantly caught.Given the layout of the city and the locations of the cops, determine if it is possible for Abushogi to reach a leaf intersection and escape.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of intersections.

The second line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$c_i \in \{0, 1\}$$$). If $$$c_i = 1$$$, there is a cop at intersection $$$i$$$. If $$$c_i = 0$$$, intersection $$$i$$$ is empty.Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$) — representing a bidirectional road between intersection $$$u$$$ and intersection $$$v$$$.

It is guaranteed that the given edges form a valid tree, and the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output "YES" if it is possible for Abushogi to reach a leaf intersection without encountering any cops. Otherwise, output "NO".

In the output, the "YES"s and "NO"s are case-insensitive, meaning that outputs such as "yEs" and "nO" are valid. However, the grid is case-sensitive.

Example
Input
3
5
0 0 1 0 0
1 2
1 3
2 4
2 5
4
1 0 0 0
1 2
2 3
3 4
1
0
Output
YES
NO
YES
Note

In the first testcase, intersection 3 has a cop. Abushogi can run $$$1 \rightarrow 2 \rightarrow 4$$$ or $$$1 \rightarrow 2 \rightarrow 5$$$ to escape.

In the second testcase, there is a cop at intersection 1, so he is instantly caught. In the third testcase, the city only has 1 intersection, and it's empty, so he is already safe.