给一个树，$n$ 个点，有点权，初始根是 1。

$m$ 个操作，种类如下：

1 x 将树根换为 $x$。

2 x y 给出两个点 $x,y$，从 $x$ 的子树中选每一个点，$y$ 的子树中选每一个点，求点权相等的情况数。

输入格式

第一行两个数表示 $n,m$。

第二行 $n$ 个数，表示每个点的点权 $a_i$。

之后 $n-1$ 行 , 每行两个数 $x,y$ , 表示一条边。

之后 $m$ 行，每行表示一个操作。

输出格式

对于每个询问，输出一个数表示答案。

样例数据

样例输入

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

子任务

Idea：nzhtl1477，Solution：nzhtl1477，Code：nzhtl1477，Data：nzhtl1477

对于 $100\%$ 的数据，$1\le n \le 10^5$，$1 \le m \le 5\times 10^5$ , $1 \le a_i \le 10^9$。