E. Color Conundrum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree $$$T$$$ with $$$n$$$ vertices rooted at vertex $$$1$$$. The vertex $$$i$$$ initially has color $$$c_i$$$. Additionally, there are $$$q$$$ queries, each of which is either of the following 2 types:

  • $$$1$$$ $$$v$$$ $$$x$$$ — Change the color of vertex $$$v$$$ to $$$x$$$.
  • $$$2$$$ $$$v$$$ $$$x$$$ — Output the number of vertices which are in the subtree of $$$v$$$ and have color $$$x$$$.
Input

The first line contains a single integer t $$$(1≤t≤2⋅10^5)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains two space separated integers $$$n$$$ $$$(1≤n≤2⋅10^5)$$$ and $$$q$$$ $$$(1≤q≤2⋅10^5)$$$.

The second line contains $$$n$$$ integers $$$c_1, c_2, ..., c_n$$$ $$$(1≤ c_i ≤n)$$$ — the initial colors of vertices.

The $$$i$$$-th of the next $$$n−1$$$ lines contains two integers $$$v_i$$$ and $$$u_i$$$ $$$(1≤ v_i,\,u_i ≤n;\, v_i≠u_i)$$$ — the $$$i$$$-th edge of the tree.

The $$$j$$$-th of the next $$$q$$$ lines contains three integers $$$type$$$, $$$v$$$ and $$$x$$$ $$$(1≤ type ≤2,\, 1≤ v ≤n,\, 1≤ x ≤n)$$$ — the $$$j$$$-th query.

It is guaranteed that the given edges form a valid tree. The sum of $$$n$$$ and sum of $$$q$$$ over all testcases do not exceed $$$2⋅10^5$$$. Also, there is atleast one $$$type\ 2$$$ query in each testcase.

Output

For each query of $$$type\ 2$$$, print a single integer — the number of vertices which have color $$$x$$$ in the subtree of $$$v$$$.

Example
Input
2
8 8
3 4 2 3 4 1 7 2
1 2
1 3
4 2
2 5
3 8
3 7
6 8
2 1 3
1 2 3
1 6 3
2 1 3
2 2 3
2 3 2
1 7 2
2 3 2
4 6
1 1 1 1
1 2
2 3
3 4
2 1 1
1 1 1
2 1 1
1 3 2
2 1 3
2 2 2
Output
2
4
2
2
3
4
4
0
1