题目描述

给定一棵 $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$，所有数值为整数。