Colored Tree

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.

Sample Input

1

3 2

1 2

2 3

1 2 3

1 2 1

2 2

Sample Output

2

Source

2019 Multi-University Training Contest 4