ADAFTBLL  Ada and Fotball
Ada the Ladybug has many friends who live on a tree. Each of them is fan of a fotball 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 ≤ 10^{5}, the number of friends (N) and the number of queries.
The next line will contain N integers 0≤ A_{i} ≤ 10^{5}, the team which i^{th} friend supports.
The next N1 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 ≤ 10^{5}), meaning that x^{th} 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.
Example Input
7 8 0 0 1 2 1 1 2 0 1 1 5 1 2 2 4 2 3 3 6 2 4 5 2 0 6 2 1 3 1 1 2 1 2 2 2 4 5 2 0 6 2 1 3
Example Output
3 2 0 2 6 3
hide comments
morass:
20171008 11:05:13
[Rampage] Blue.Mary: Good day to you, and sorry for inconvenience.


[Rampage] Blue.Mary:
20171008 09:50:44
" 0 ≤ a b ≤ N " actually means " 0 ≤ a b < N and a != b"?

Added by:  Morass 
Date:  20171008 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Tunisian Collegiate Training Contest  Round #01 