Youare given a tree with N nodes. The tree nodes are numbered from 1 to N and have colors C1, C2, ..., CN initially. You have to handle M instructions on the tree of the following forms: • 0 u c: Changethecolorofnodeutoc. • 1 u v: Output the maximum number of times a color appeared on the unique path from node u to node v. Input The first line of input contains T (1 ≤ T ≤ 10) which is the number of test cases. The first line of each test case contains two integers N and M (1 ≤ N, M ≤ 105). Next line contains N space separated integers C1, C2, ..., CN (1 ≤ Ci ≤ 10) denoting the initial colors of the nodes. Each of the next N − 1 lines contain two integers a and b (1 ≤ a,b ≤ N and a ̸= b) meaning that there is an edge between node a and node b. Each of the next M lines contains an instruction of one of the two forms described above. Foralltheinstructions: 1≤u,v≤N and1≤c≤10. Output For each of the second type instruction output the answer in one line. Sample Input 2 56 32123 12 23 24 15 135 011 021 135 024 124 21 56 12 122 Sample Output 2 3 1 1