Alu will be given a rooted tree where each node contains an integer value of 0 or 1. He can perform flip operations at some nodes. This operation will flip the value of the selected node and the values of all the children of the selected node once. Flipping a value means changing 0 to 1 or 1 to 0. Alu is intelligent so he performs this operation the minimum number of times to make the values of all nodes zero.

However, it's not fun if the tree is static. So here comes Begun into the scene. He has a tree. He can perform following updates on his tree:

• Update 1: Begun flips the value of a particular node (note, the value of the children of the selected node are not flipped).
• Update 2: Begun makes a particular node the root of the tree.

After each update, you need to output the minimum number of operations Alu requires to perform to make the tree zero. Note, Alu does not change the Begun's tree. You may imagine that Alu performs his operations on a copy of Begun's tree.

Input begins with the number of test cases, T. Each case begins with two positive integers, the number of nodes n and the number of updates q. Next line contains n integers, the i'th integer is the value of the i'th node.

Each of the next n - 1 lines consists of two integers: u and v. These describe the edges of the tree. Each of the next q lines contains two integers: id x. id = 1 denotes Update 1 and id = 2 denotes Update 2. x denotes the node on which the update is performed. You may assume that the input tree is valid. Initially, 1 is the root of the tree.

Constraints

• 1 ≤ T ≤ 10,000
• Sum of n overall test cases ≤ 100,000
• Sum of q overall test cases ≤ 100,000
• 1 ≤ id ≤ 2
• 1 ≤ x ≤ n
• 1 ≤ u, v ≤ n

For each case print the case number. Then for each update, print the answer.