Problem Description

There is a tree with vertex 1 as a root. All vertices of the tree are colored.
Your task is to determine the number of sub-trees with exactly k distinct colors.
There are two types of queries.
1 u c : paint vertex u with color c.
2 k : answer the query.

Input

The first line of input contains an integer T (1 <= T <= 5) denoting the number of test cases.
The first line of each test case contains two integers N and Q (1 <= N, Q <= 100000), the number of vertices in the given tree and the number of queries respectively. Each of the next N - 1 lines contains two integers u and v, representing that there exists an edge between vertex u and v.
The next line contains N space-separated integers and the i-th integer denotes the color of vertex i.
Then Q lines followed and each line consists of one of two types of queries.

Output

For each query of type 2, output the answer in one line.

1
3 2
1 2
2 3
1 2 3
1 2 1
2 2

2