Tree Play!

Hey, Bessie and Cowchops are playing a game -- not under, but _with_ a tree...

The rules are simple: Two cows take turns severing edges of a tree.
Some nodes are initially designated as "on the ground."

When a player cuts an edge, all the edges that are no longer connected to
the ground (that is, the nodes "on the ground") disappear. The player who first can not make a move loses.

Bessie plays first and both Bessie and Cowchops are very good players. 

If you know state of the tree they are playing with, can you determine who will win?

PROBLEM NAME: play

INPUT FORMAT:

* Lines 1..end of input: 

Input consists of multiple test-cases. The first line contains one integer t - number of cases (0 < t <= 20). For each case, the input format is following. 

The first line contains one integer N (1 <= N <= 100000).
        
The next line contains N integers s_i (1 or 0). If s_i is 1, the ith node is on the ground. If s_i is 0, the ith node is not on the ground. 

Each line of the following N - 1 lines contains two integers u, v. These numbers denote that there is an edge between node u and node v (1 <= u, v <= N ). There is not a blank line after each case: they run one into the next... .

SAMPLE INPUT:

1
4
0 0 0 1
1 2
2 3
2 4

OUTPUT FORMAT:

* Lines 1..end of output: For each case, output who will win the game.
        If Bessie wins, output 1; otherwise, output 0 (Cowchops wins).

SAMPLE OUTPUT:

1