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.

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.

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