该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

由于上题做的太慢，石老板没有得到及时的抢救，现在他的魂来找你复仇了......

给定一棵 $n$ 个节点的树，第 $i$ 个点有点权 $a_i$。

定义一个点 $x$ 所在的极大同色连通块为一个极大的点集 $S$，满足 $x\in S$，且对任意点集中的元素 $i,j$，可以找到一个节点序列 $p_1,p_2,...p_t$，满足 $p_1=i$，$p_t=j$，且对任意 $k$ 为 $[1,t)$ 中的整数，满足 $p_k$ 与 $p_{k+1}$ 在树上相邻，且 $a_{p_k}=a_{p_{k+1}}$，且 $p_k\in S$。

有 $m$ 次操作：

1 x y：给出一个点 $x$ ，将其所在的极大同色连通块中每个点的点权修改为 $y$。

2 x：给出一个点 $x$，查询其所在的极大同色连通块的大小。

输入格式：

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

第二行 $n-1$ 个数，第 $i$ 个数表示树上第 $i+1$ 的节点的父亲节点的编号，保证父亲节点的编号比该节点小。

第三行 $n$ 个数，第 $i$ 个数表示 $a_i$。

之后 $m$ 行，每行形如 1 x y 或 2 x，意义如上述。

输出格式：

对每个 $2$ 操作，输出一行一个数表示答案。

样例

输入样例

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

输出样例

2
4

数据范围

ex_test2.in/ex_test2.ans​ 对应下面 $20\%$ 数据的部分。

ex_test3.in/ex_test3.ans​ 对应下面 $100\%$ 数据的部分。

对于前 $20 \%$ 的数据，保证 $n,m \leq 1000$。

对于前 $40 \%$ 的数据，保证 $n,m \leq 100000$。

对于另外 $30\%$ 的数据，保证 $1\le a_i\le 2$。

对于$100\%$的数据，满足 $1\le n,m\leq 10^6$，$1\le a_i\le n$。

样例下载