Tahsin and Tree

CLown1331 Replay of 18th IUT Comput...
Limits 1s, 512 MB

Tahsin loves graph theory very much. He is especially fond of trees. For his upcoming birthday his friends decided to gift him a tree, lets call it birthday tree. Birthday tree consists of nn node numbered 1 to nn, having a light in every node. Initially some of the light is turned on and some are turned off. Root of the tree is 1.

The tree has a special property, when a node is toggled, all the children of the node is also toggled. So if you toggle the node ii, you also toggle the children of ii and so on.

In order to help Tahsin understand the tree better, you are going help him process qq queries.

Input

Input starts with TT (1T51 \le T \le 5).

The first line of every test contains two integers nn (1n1051 \le n \le 10^5) and qq (1q1051 \le q \le 10^5). The second line contains nn integers a1a_1, a2a_2, ..., ana_n, where aia_i is the initial state of the node ii. Each of the next n1n-1 lines contains two integer uiu_i and viv_i (1ui,vin1 \le u_i, v_i \le n), meaning there is an edge between uiu_i and viv_i.

Each of the next qq line contains an integer xx (1xn1 \le x \le n), the node to be toggled.

Output

For each case, after processing all the queries, print nn integer b1b_1, b2b_2, ..., bnb_n, denoting the status of the node.

See the sample test case for input output format.

Sample

InputOutput
1
4 1
0 1 1 0 
1 4
2 1
3 1
1
Case 1: 1 0 0 1

Submit

Login to submit.

Contributors

Statistics

86% Solution Ratio
shaheen_bdEarliest, Oct '17
mahabub.tweetFastest, 0.1s
a.salamLightest, 5.1 MB
shakil07Shortest, 725B
Toph uses cookies. By continuing you agree to our Cookie Policy.