BUET Inter-University Programming Contest

Problem A – Answering Queries on a Tree

 

Problem

You are 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: Change the color of node u to c.

·         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  which is the number of test cases. The first line of each test case contains two integers N and M . Next line contains N space separated integers C1, C2, … CN  denoting the initial colors of the nodes. Each of the next N-1 lines contain two integers a and 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. For all the instructions: .

 

Output

For each of the second type instruction output the answer in one line.

Sample Input

Output for Sample Input

 

2

5 6
3 2 1 2 3
1 2
2 3
2 4
1 5
1 3 5
0 1 1
0 2 1
1 3 5
0 2 4
1 2 4
2 1
5 6
1 2
1 2 2

2
3
1
1

 

Problemsetter:

Tasnim Imran Sunny

Special Thanks:

Muntasir Mashuq and Tanaeem M Moosa