题目描述

菜哭武的后花园里种着一棵树，这棵树有 $n$ 个节点和 $n-1$ 条边，每个节点都涂着一种颜色。菜哭武打算在接下来的 $m$ 天里，每天执行以下两个操作之一：

1. 菜哭武选择某一种颜色和树上的某一个节点，将这个节点涂上这种颜色（会将该节点原有的颜色覆盖）。
2. 菜哭武选择一种颜色，然后询问这棵树上由所有涂着这种颜色的节点构成的子树含有多少个节点（原树上的某个点集 $S$ 构成的子树 $T$ 的定义是：如果 $u \in S$，$v \in S$，那么原树 $u$ 和 $v$ 路径上的所有点都属于这棵子树 $T$）。如果这棵树上没有这种颜色的节点，那么定义询问的结果为 $0$。

输入格式

第一行两个整数 $n$ 和 $m$（$1 \leq n, m \leq 10^5$），分别代表树的节点个数和天数。

第二行到第 $n$ 行，每行两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），代表节点 $u$ 和 $v$ 之间有一条边。

第 $n + 1$ 行有 $n$ 个整数，用空格隔开，第 $i$ 个数代表节点 $i$ 初始涂的颜色 $c_i$（$1 \leq c_i \leq n$）。

接下来 $m$ 行，每行开头一个数 $op$，代表操作的类型。$op = 1$ 代表涂色，$op = 2$ 代表询问。

若 $op = 1$，接下来会有两个整数 $x$ 和 $y$（$1 \leq x, y \leq n$），代表将节点 $x$ 涂成颜色 $y$。

若 $op = 2$，接下来会有一个整数 $x$，代表询问颜色为 $x$ 的节点构成子树含有的节点个数。

输出格式

对于每一个 $op = 2$ 的操作，输出一行整数，代表询问的结果。

样例输入

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

样例输出

4
0
1
1