题目背景

题目描述

对于一个节点 $i$ 存在二元组信息 $(a_i,b_i)$。

给定大小为 $n$ 的树。初始化所有节点全为 $(0,0)$。根为 $1$。

给定 $m$ 个操作。

• $1 \ x \ c$ 设当前操作编号为 $z$，对于 $x$ 到根路径，路径上的所有节点 $i$ 的二元组信息，若 $a_i = c$ 那么令 $(a_i,b_i) \leftarrow (c,b_i)$ 否则令 $(a_i,b_i) \leftarrow (c,z)$。

• $2 \ x$ 查询 $(a_x,b_x)$。

输入格式

第一行两个整数 $n,m$ 代表树的大小和操作个数。

接下来一行 $n - 1$ 个数，第 $i$ 个数 $p_i$ 表示点 $i + 1$ 的父亲 $p_i$。

接下来 $m$ 行，每行三个数或两个数代表操作。

输出格式

对于每个询问，输出一行两个数表示答案。

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

0 0
0 0
3 2
3 2

提示

Idea： FutaRimeWoawaSete，Solution： FutaRimeWoawaSete，Code： FutaRimeWoawaSete，Data： FutaRimeWoawaSete

【数据范围】

特殊性质 $A$：满足 $p_i$ 从 $[1,i - 1]$ 里随机选择。

特殊性质 $B$：保证所有 $1$ 操作中 $c = 1$。

特殊性质 $C$：保证 $p_i = i - 1$。

所有数据保证 $n,q \leq 10 ^ 6,x,c \in [1,n]$。

保证样例 $2,3,4,5$ 相应性质对应测试点 $1 \sim 5,6 \sim 10,11 \sim 15,16 \sim 20$ 且使用同一构造方式生成。