You are given an undirected tree $G$ with $N$ nodes. Every node is assigned a value denoted by $A[i]$.

A simple path $u_1 - u_2 - u_3 - u_4, .. ,- u_k$ is said to be beautiful if the number of pairs of nodes $(u_i, u_{i+1})$ where $A[u_i]$ is odd and $A[u_{i+1}]$ is even and number of pairs of nodes $(u_i, u_{i+1})$ where $A[u_i]$ is even and $A[u_{i+1}]$ is odd are equal.

Given $Q$ queries of the form:

• $u \ \text{val}$: Set the value of node $u$ equal to $\text{val}$, i.e. set $A[u] = \text{val}$ and find the number of ordered pairs $(u, v)$ such that the simple path between node $u$ and node $v$ is beautiful.

Note: 

• Assume 1 based indexing.
• Queries are interdependent, changes made in previous queries are retained.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• For each test case:
  • The first line contains two space-separated integers $N \ Q$ denoting the number of nodes in the tree and the number of queries respectively.
  • Next line contains $N$ space-separated integers denoting the array $A$.
  • Next $N - 1$ lines contain two space-separated integers $a \ b$, denoting an edge between node $a$ and node $b$. 
  • Next $Q$ lines contains the queries.

Output format

For each test case in a new line, print the answer for queries in a space-separated format.

Constraints

$1 \le T \le 10 \\ 1 \le N, Q \le 2 \times 10^5 \\ 1 \le A[i], val \le 10^9 \\ 1 \le u \le N \\ $