11571157 SUSTech Online Judge
Problem 1157 --Game [Hard]

1157: Game [Hard]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 573  Solved: 161
[Submit][Status][Web Board]

Description

Hong likes game very much. He wants to play a game with you.

There is a tree with N nodes. Node 1 is the root. Each node is colored black or white.

Each turn, the player should choose a black node and change it to white. After that, he can choose its any number of the proper ancestors and change their color. The one who cannot find a black node at the tree in his turn, he lose the game.

Hong is good at the game, so he let you take the first turn. Hong will always find the optimal solution. He wants to know if you can win the game.

Input

The first line will be an integer T (1≤T≤100), which is the number of test cases.

For each test data:

The first line contains one integer N (1≤N≤10000) — the number of the nodes.

The second line contains N integers w1…wn {0, 1}, wi = 1 means node i is black. Otherwise node i is white.

Each of the next N - 1 lines contain two integers a and b, which means there is an edge between node a and b.

Output

For each teat case, if you can win, print “YES”; Otherwise, print “NO”.

Sample Input

1
2
1 0
1 2

Sample Output

YES

HINT

Source

Lab6 Tree 

[Submit][Status]