PT07A - Play with a Tree

no tags 

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

hide comments
Joshi Cordova Monroy: 2013-05-06 02:40:49

Does the input contain only one tree per test case ? And is it strictly a tree or can it contain loops ?

Piyush Kapoor: 2012-05-15 17:49:16

Not at all an easy problem !!!

Jonathan Schmidt-Dominé: 2011-12-04 20:32:29

“Some nodes is on the ‘ground’.”
Does that mean that mean there is only one node on the ground, or many nodes?

Rafa³ Bielenia: 2010-07-11 18:04:55

TL is too strict!
Please fix it.

Last edit: 2010-07-13 22:50:53

Added by:Thanh-Vy Hua
Date:2007-04-07
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Co-author Amber