题目

题目描述

HJWJSSB 成年了，父母觉得他是时候去找一个喜欢的人。 他遇到了室友 HAO，在和HAO 一起同居的两年， HJWJSSB 不知不觉中对 HAO 产生了一点好感。 后来 HJWJSSB 换了一个公司，遇到了同事 ciewai。 ciewai 对他很好，经常加班陪他，等他一起回家， HJWJSSB 接触 ciewai 这么久后，也感觉 ciewai 对自己有一些爱慕，可是他又有点放不下 HAO，于是他找到了他曾经的王者，问他怎么办，王者用他智慧的大脑说为了你的后代考虑，你应该给他们出一道题，若谁先做出这道题，谁的智商就更高一些，这样你就能更好的选择。。。

于是 HJWJSSB 拿着王者出的题给了 ciewai 和 HAO，然而 ciewai 很蠢， HAO 很聪明，但是 ciewai 却不想认输，于是 ciewai 找到聪明的你，求你来帮帮 ciewai，让 ciewai 获得真爱。。。

王者出的题目是这样的：

给一颗$n$个点的树，每一个点有一个颜色，然后维护几个操作。

• 操作$1$：$t=1$时，将$x$点的颜色修改为$y$；
• 操作$2$：$t=2$时，询问$x$到$y$路径上有多少个不同的颜色段；
• 操作$3$：$t=3$时，询问$x$到$y$路径上的出现次数最多的颜色的出现次数。

输入描述

第一行两个数$n, Q$，分别表示树的点数和操作个数。

第二行$n$个数，分别表示每个点的颜色。

第$3$行到第$n + 1$行每行两个数$x, y$表示$x$到$y$有一条无向边。

第$n + 2$行到第$n + Q + 1$行每行$3$个数$t, x, y$。

输出描述

输出的行数为询问个数。

每一行输出当前询问的答案。

样例输入

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

样例输出

3
2
2

数据范围

对于$20\%$的数据，$1 \leq n \leq 100$，$1 \leq Q \leq 100$；

另有$15\%$的数据，树是一条链，只有操作$1$和操作$2$；

另有$15\%$的数据，只有操作$1$和操作$2$；

另有$15\%$的数据，树是一条链，只有操作$1$和操作$3$；

另有$15\%$的数据，只有操作$1$和操作$3$；

对于$100\%$的数据，$1 \leq n \leq 100000$，$1 \leq Q \leq 100000$，$0 \leq 颜色大小 \leq 100000$。

后记

最后在你的帮助下 ciewai 赢了 HAO，可是 HJWJSSB 还是十分犹豫，于是他去问了他曾经的王者，王者告诉他说既然你觉得很难选择，那就不如都选择！！！

于是 HJWJSSB 和 ciewai，还有 HAO 幸福快乐的生活在了一起。。。。。。

Orz 祯哥，祝祯哥早日得到妹子的认可， NOI 进队！！！