#6814. 「THUPC 2022 初赛」赫露艾斯塔

题目描述
给定一棵 $n$ 个顶点的有根树，顶点编号为 $1, 2, \dots, n$，$1$ 号顶点为根。定义有向邻域 $N(x, y)$ 为以 $x$ 为根的子树中，距离 $x$ 小于 $y$ 的顶点构成的集合，其中 $1 \le x \le n$，$0 \le y \le n$，$x, y$ 为整数。

给出 $m$ 个有向邻域 $N(x_i, y_i)_{i=1}^m$，你可以从 $N(1, 0)$（根据定义，这是一个空集）出发，经过不超过 $5m$ 次操作到达每个给出的有向邻域，可以使用的操作有：

1. 从有向邻域 $N(x, y)$ 移动到 $N(x', y')$，满足 $N(x, y) \subseteq N(x', y')$；
2. 撤销一次操作 1，即回到之前最后一次未撤销的操作 1 前的位置，并将这次操作 1 标为已撤销；
3. 声明当前到达了有向邻域 $N(x_i, y_i)$，满足当前所在邻域是 $N(x_i, y_i)$；

其中操作 1 的代价为移动前后两个有向邻域的元素个数之差，操作 2 和 3 不计代价，要求操作 2 执行时必须存在未撤销的操作 1，操作 3 必须对每个 $1 \le i \le m$ 恰好各执行一次。

你需要保证操作的总代价不超过 $2.5 \times 10^9$。

输入格式
第一行两个整数 $n\ m$；
接下来一行，共 $n-1$ 个整数，依次表示编号为 $2, 3, \dots, n$ 的顶点的父亲 $f_2, \dots, f_n$，保证父亲的编号小于孩子的编号；
接下来的 $m$ 行中，第 $i$ 行两个整数 $x_i\ y_i$，表示给出的每个有向邻域。

输出格式
第一行一个整数 $m'$，表示你进行的操作次数；
接下来 $m'$ 行，依次表示每个操作；
操作 1 表示为 1 x' y'；
操作 2 表示为 2；
操作 3 表示为 3 i。

样例
输入

8 4
1 1 1 2 2 2 5
2 1
1 1
6 0
1 2

输出

16
1 2 1
3 1
2
1 6 0
3 3
2
1 1 1
1 1 1
3 2
2
1 1 2
1 1 2
3 4
2
2
2

数据范围与提示
对于 $100\%$ 的数据，满足 $1 \le n, m \le 10^6$，$1 \le f_i \le i - 1$，$1 \le x_i \le n$，$0 \le y_i \le n$，所有数值为整数。