新年假期结束了,但瑞莎不想扔掉新年树。他邀请了最好的朋友克里姆和古拉尔帮他重新装饰新年树。
新年树是一棵有 n 个顶点、根在顶点 1 的无向树。
您应该处理两种类型的查询:
1.将顶点v的子树中所有顶点的颜色更改为颜色c。
2.求顶点v的子树中不同颜色的数量。
输入
第一行包含两个整数 n, m (1 ≤ n, m ≤ 4·105) — 树中的顶点数和查询数。
第二行包含 n 个整数 ci (1 ≤ ci ≤ 60) — 第 i 个顶点的颜色。
接下来的 n - 1 行中的每一行都包含两个整数 xj, yj (1 ≤ xj, yj ≤ n) — 第 j 条边的顶点。保证您获得正确的无向树。
最后 m 行包含查询的描述。每个描述都以整数 tk (1 ≤ tk ≤ 2) 开始——第 k 个查询的类型。对于第一种类型的查询,后面跟着两个整数 vk, ck (1 ≤ vk ≤ n, 1 ≤ ck ≤ 60) — 其子树将用颜色 ck 重新着色的顶点的编号。对于第二种类型的查询,则遵循整数 vk (1 ≤ vk ≤ n) — 您应该找到其子树的不同颜色数量的顶点数。
输出
对于第二种类型的每个查询,打印整数 a — 查询中给出的顶点的子树中不同颜色的数量。
每个数字都应按照输入中出现的查询顺序打印在单独的行上。
示例
输入 #1
7 10 1 1 1 1 1 1 1 1 2 1 3 1 4 3 5 3 6 3 7 1 3 2 2 1 1 4 3 2 1 1 2 5 2 1 1 6 4 2 1 2 2 2 3
输出 #1
2 3 4 5 1 2
输入 #2
23 30 1 2 2 6 5 3 2 1 1 1 2 4 5 3 4 4 3 3 3 3 3 4 6 1 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10 4 11 6 12 6 13 7 14 7 15 7 16 8 17 8 18 10 19 10 20 10 21 11 22 11 23 2 1 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 4 1 12 1 1 13 1 1 14 1 1 15 1 1 16 1 1 17 1 1 18 1 1 19 1 1 20 1 1 21 1 1 22 1 1 23 1 2 1 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 4
输出 #2
6 1 3 3 2 1 2 3 5 5 1 2 2 1 1 1 2 3