How can i solve this problem from spoj?

Ada the Ladybug has many friends who live on a tree. Each of them is fan of a football team. Ada sometime go on a trip from one friend to another. If she meets a friend she tells him/her about all previously visited friends who are fans of the same team. The visited friend will gain +1 happiness for each friend Ada told him/her about.

Ada is wondering (for each trip) what will be the total gaines happiness.

Also note that sometime a friend changes his/her mind and start to support different team.

Input

The first line two integers 1 ≤ N Q ≤ 105 , the number of friends ( N ) and the number of queries.

The next line will contain N integers 0≤ Ai ≤ 105 , the team which ith friend supports.

The next N-1 lines will contain two integers 0 ≤ a, b < N , the friends which will be connected by a branch (edge).

The next Q lines will be of two kinds:

1 x y ( 0 ≤ x < N , 0 ≤ y ≤ 105 ), meaning that xth friend will start supporting team y (instead of the old one).

2 a b ( 0 ≤ a, b < N ), meaning that Ada will travel from friend a to friend b and wants to know the happiness.

Output

For each query of second kind, output the gained happiness.