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 ≤ 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.

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: 2017-10-08 11:05:13

[Rampage] Blue.Mary: Good day to you, and sorry for inconvenience.

a) Yes, you are right, thank you

b) Seems to be so, thank you [Please try to resubmit and again, sorry for inconvenience]

Last edit: 2017-10-08 11:13:36
[Rampage] Blue.Mary: 2017-10-08 09:50:44

" 0 ≤ a b ≤ N " actually means " 0 ≤ a b < N and a != b"?
"1 x y (0 ≤ x ≤ N ..." actually means "1 x y (0 ≤ x < N ..."?

(Btw, are you sure all your test cases are right?)

Last edit: 2017-10-08 10:15:39

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