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 \\ \)