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.