Description

You are playing a galgame, and then your parents suddenly come in, so you pretend you are solving a data structure problem.

Given a tree with $n$ nodes. Each node has a weight. The initial root is $1$.

There are $m$ operations of the following types:

1 x Change the root of the tree to $x$.

2 x y Given two nodes $x, y$, choose every node from the subtree of $x$ and every node from the subtree of $y$, and count the number of pairs whose node weights are equal.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers, where the $i$-th integer is the node weight $a_i$.

The next $n-1$ lines each contain two integers $x, y$, indicating an edge.

The next $m$ lines each describe one operation.

Output Format

For each query, output one integer representing the answer.

5 5
1 2 3 4 5
1 2
1 3
3 4
3 5
2 4 5
2 1 5
2 3 5
1 5
2 4 5

0
1
1
1

Hint

Idea: nzhtl1477, Solution: nzhtl1477, Code: nzhtl1477, Data: nzhtl1477

Constraints
For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 5 \times 10^5$, $1 \le a_i \le 10^9$.

Translated by ChatGPT 5