Bob's Colorful Tree Queries

Bob has a rooted tree with \(n\) nodes, where node 1 is the root. Each node is painted with a distinct color initially. The weight of a path is defined as the number of distinct colors among the nodes on that path (including both endpoints).

Bob will perform \(m\) operations on the tree. The operations are in one of the following forms:

• 1 x: Repaint all nodes on the path from node \(x\) to the root with a new color that has not been used before.
• 2 x y: Query the weight of the path from node \(x\) to node \(y\).
• 3 x: In the subtree rooted at node \(x\), select a node such that the weight of its path to the root is maximized, and output that maximum weight.

You are given the initial tree structure and the \(m\) operations. Initially, the color of node \(i\) is \(i\) (i.e. the colors are \(1, 2, \dots, n\)).

Note: The tree is given by providing the parent for every node except the root.

---

Input Format

The first line contains two integers \(n\) and \(m\).

The second line contains \(n-1\) integers, where the \(i\)th integer (for \(2 \le i \le n\)) represents the parent of node \(i\). It is guaranteed that the tree is rooted at node 1.

The following \(m\) lines each describe an operation in one of the following forms:

• 1 x
• 2 x y
• 3 x

---

Output Format

For each operation of type 2 and type 3, output the corresponding answer on a new line in the same order as the operations appear.

inputFormat

The input begins with a line containing two integers \(n\) and \(m\) (the number of nodes and the number of operations).

The next line contains \(n-1\) integers: \(p_2, p_3, \dots, p_n\), where \(p_i\) is the parent of node \(i\).

Then follow \(m\) lines, each representing an operation. The operations are given in one of the following forms:

• 1 x: Repaint the path from \(x\) to the root with a new color.
• 2 x y: Query the weight (number of distinct colors) on the path from node \(x\) to node \(y\).
• 3 x: Query the maximum weight among all paths from a node in the subtree of \(x\) to the root.

outputFormat

For each query operation of type 2 and 3, output a single integer on a new line representing the answer.

sample

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

5
3
3
3

</p>