Constructing a Valid Operation Sequence

You are given a rooted tree with n vertices numbered from 1 to n. Vertex 1 is the root. For any vertex x and non‐negative integer y, define the directed neighborhood N(x, y) as the set of vertices in the subtree of x (with root x) whose distance from x is less than y (i.e. all vertices v in the subtree of x with d(x, v) < y). Note that when y = 0 the set is empty.

You are also given m directed neighborhoods: N(x₁, y₁), N(x₂, y₂), …, N(xₘ, yₘ). Starting from the initial neighborhood N(1, 0), you are allowed to perform at most 5m operations in order to reach each of the given neighborhoods. There are three kinds of operations:

1. Operation 1 (Move): Switch from the current neighborhood N(x, y) to another neighborhood N(x', y') provided that N(x, y) ⊆ N(x', y'). The cost of this operation is |N(x', y')| − |N(x, y)|, that is, the difference in the number of elements in the two neighborhoods.
2. Operation 2 (Undo): Undo the most recent (and not yet undone) Operation 1. After undoing, you return to the neighborhood you were at before that Operation 1. (This operation has no cost.)
3. Operation 3 (Declare): Declare that the current neighborhood is exactly one of the target neighborhoods N(xᵢ, yᵢ). You must perform Operation 3 exactly once for each 1 ≤ i ≤ m (in some order). (This operation is free.)

Your task is to provide an operation sequence which, starting from N(1, 0), reaches every target neighborhood (by performing Operation 3 for each) within at most 5m total operations and with a total cost (i.e. the sum of costs of all Operation 1 moves) not exceeding 2.5×10⁹.

Input Format: The first line contains two integers n and m. The second line contains n − 1 integers where the iᵗʰ integer (for i = 2,…,n) is the parent of vertex i in the tree. The following m lines each contain two integers xᵢ and yᵢ, representing the target neighborhood N(xᵢ, yᵢ).

Output Format: First, output an integer k representing the total number of operations in your sequence. Then output k lines, each describing an operation. There are three types of operations:

• 1 x y: Perform Operation 1 to move to neighborhood N(x, y).
• 2: Perform Operation 2 (undo the last unmatched Operation 1).
• 3 i: Perform Operation 3 to declare that the current neighborhood equals target neighborhood N(xᵢ, yᵢ) (1-indexed).

You do not need to minimize the number of operations as long as you do not exceed 5m operations and the total cost of all Operation 1 moves does not exceed 2.5×10⁹.

Note: The neighborhood N(1, 0) is empty, and since the empty set is a subset of every set, you can always use Operation 1 from the initial state to any target neighborhood. One simple strategy is, for each target neighborhood, to move directly from N(1, 0) to N(xᵢ, yᵢ) (Operation 1), declare it (Operation 3), and then undo the move to return to N(1, 0) (Operation 2). This uses 3 operations per target, which is within the limit.

inputFormat

The input begins with a line containing two space-separated integers n and m, where 1 ≤ n ≤ (some upper limit) and 1 ≤ m ≤ (some upper limit).

The second line contains n − 1 integers. For each i from 2 to n, the iᵗʰ integer denotes the parent of vertex i in the tree.

Then follow m lines. The iᵗʰ of these lines contains two integers xᵢ and yᵢ (with 1 ≤ xᵢ ≤ n and 0 ≤ yᵢ ≤ n) representing the target directed neighborhood N(xᵢ, yᵢ).

outputFormat

First, output an integer k indicating the total number of operations in your sequence. Then output k lines, each representing an operation. The operations should be one of the following types:

• 1 x y — Operation 1: move to neighborhood N(x, y).
• 2 — Operation 2: undo the last unmatched Operation 1.
• 3 i — Operation 3: declare that the current neighborhood equals target neighborhood number i (1-indexed).

Your sequence must use no more than 5m operations and the total cost of all Operation 1 moves must not exceed 2.5×10⁹.

sample

3 1
1 1
1 2

3
1 1 2
3 1
2

</p>