PT07A - Play with a Tree

Hey, ACRush and Jelly are playing a game ! Let take a look at its rule:

You are given a tree. Two players take turns cutting edges on a tree. Some nodes is on the "ground". When a player cuts an edge, all the edges that are no longer connected to the ground disappear. The player who can not take a move loses.

ACRush plays first. Both of them are very good players. If you know state of the tree they are playing with, can you guess who will win?

Node 4 is on the ground.

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 N integers s[i] (1 or 0). If s[i] is 1, the i-th node is on the ground. If s[i] is 0, the i-th node is not on the ground. Each line of the following N - 1 lines contains two integers u, v. They denote there is an edge between node u and node v (1 <= u,v <= N).
There is no blank line after each case.

Output

For each case, output who will win the game. If ACRush wins, output 1; otherwise, output 0 (Jelly wins).
There is no blank line after each case.

Example

Input:
1
4
0 0 0 1
1 2
2 3
2 4

Output:
1

Added by:Thanh-Vy Hua
Date:2007-04-07
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:Co-author Amber

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.