Problem Description

Given a rooted tree with $n$ vertices numbered $1,2,\dots,n$, where vertex $1$ is the root. Define the directed neighborhood $N(x,y)$ as the set of vertices in the subtree rooted at $x$ whose distance to $x$ is less than $y$, where $1\le x\le n,\;0\le y\le n$, and $x,y$ are integers.

You are given $m$ directed neighborhoods $N(x_i,y_i)_{i=1}^m$. Starting from $N(1,0)$, you need to reach every given directed neighborhood using no more than $5m$ operations. The allowed operations are:

1. Move from a directed neighborhood $N(x,y)$ to $N(x',y')$, such that $N(x,y)\subseteq N(x',y')$.
2. Undo one operation of type 1, i.e., return to the position before the most recent not-yet-undone type 1 operation, and mark that type 1 operation as undone.
3. Declare that you have currently reached the directed neighborhood $N(x_i,y_i)$, where your current neighborhood equals $N(x_i,y_i)$.

For operation 1, the cost is the difference between the sizes (number of elements) of the two directed neighborhoods before and after the move. Operations 2 and 3 have no cost. When performing operation 2, there must exist a type 1 operation that has not been undone. Operation 3 must be performed exactly once for each $1\le i\le m$.

You must ensure that the total cost of all operations does not exceed $2.5\times{10}^{9}$.

Input Format

The first line contains two integers $n\ m$.

The next line contains $n-1$ integers, which are the parents $f_2,\dots,f_n$ of vertices $2,3,\dots,n$ in order. It is guaranteed that the parent index is smaller than the child index.

The next $m$ lines each contain two integers $x_i\ y_i$. Line $i$ describes the given directed neighborhood.

Output Format

The first line contains an integer $m'$, the number of operations you perform.

The next $m'$ lines describe each operation in order.

Operation 1 is written as $1\ x'\ y'$.

Operation 2 is written as $2$.

Operation 3 is written as $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

Hint

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078, SPJ: nalemy.

For $100\%$ of the testdata, $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$. All values are integers.

Translated by ChatGPT 5