#216079. [CSPro 33] 文件夹合并

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

新入职西西艾弗岛有限公司的小 C 接替了刚刚升职的小 S 的项目。然而小 C 打开项目工程时，一层层嵌套的文件夹让小 C 感到眼花缭乱。为了精简项目结构，小 C 决定对项目的文件夹进行一些必要的合并。

项目中共有 个文件夹。为了方便，我们用 至 的整数给这 个文件夹编号，其中编号为 的文件夹为项目的根文件夹，其他每个文件夹都有一个父文件夹，这些文件夹构成了树形结构。除了子文件夹以外，第 个文件夹内还直接存储了 字节的数据。

小 C 进行了若干次文件夹合并操作。每次操作中小 C 会选择一个文件夹 ，将这个文件夹和它的所有子文件夹合并。具体地，小 C 会进行以下操作：遍历 的子文件夹 ，将文件夹 包含的所有文件夹和文件移动到文件夹 ，然后删除文件夹 。所有文件和文件夹的名称是两两不同的，合并过程中不需要考虑文件或文件夹重名的情况。在每一次合并操作后，小 C 需要知道文件夹 内共有几个文件夹以及多少字节的数据。

例如，考虑以下项目：根文件夹内有文件夹 和文件夹 以及 字节数据，其中文件夹 为空文件夹，文件夹 内有 字节数据和文件夹 ，文件夹 包含 字节数据。对根文件夹进行一次合并后，文件夹 和文件夹 被合并至根文件夹，此时根文件夹下有文件夹 以及 字节数据，而文件夹 下也包含 字节数据。

在合并文件夹的过程中，小 C 常常需要访问某个文件夹 下的文件。此时，小 C 会从根文件夹开始，每次进入当前文件夹的一个子文件夹。小 C 需要知道按照以上过程，获取到文件夹 下的文件至少需要经过多少个文件夹。

例如，在以上项目中，未对根文件夹进行合并前，访问根文件夹下的文件只需要经过根文件夹一个文件夹，而访问文件夹 则需要经过根文件夹以及文件夹 和 。而对根文件夹进行合并之后，访问文件夹 只需要经过根文件夹和文件夹 了。

在整个项目中，小 C 一共进行了 次文件夹合并以及文件访问操作。你需要帮助小 C 正确维护文件夹之间的关系，并在每次操作后正确回答小 C 需要的数据。

从标准输入读入数据。

输入的第一行两个整数 ，分别表示文件夹数量以及操作次数。

第二行 个整数 ，其中 表示文件夹 的父文件夹编号。

第三行 个整数 ，其中 表示文件夹 中数据的存储量。

接下来 行第 行两个整数，第一个整数 表示操作类型。若 则表示一次文件夹合并操作，接下来一个整数 表示合并的文件夹编号；若 则表示一次文件访问操作，接下来一个整数 表示访问的文件夹编号。

输出到标准输出。

输出 行，第 行表示第 个操作中小 C 需要的数据：若 则输出两个整数，依次表示文件夹 的子文件夹数量以及数据的存储量；若 则输出一个整数表示小 C 获取文件夹 下的数据最少需要经过的文件夹个数。

样例输入 1

4 6
1 1 3
100 0 200 300
2 1
2 4
1 1
2 4
1 1
1 1

样例输出 1

1
3
1 300
2
0 600
0 600

子任务

对于所有测试数据，

• ,
• ，输入的文件夹结构构成树形结构，
• ,
• ，每次合并操作中给出的文件夹 没有被删除，每次文件访问操作中给出的文件夹 没有被删除。

特殊性质 A：。

特殊性质 B：。

特殊性质 C：在文件夹合并操作中，。

特殊性质 D：，即没有文件访问操作。

特殊性质 E：，即没有文件夹合并操作。