Dynamic Tree Set Decomposition

You are given a rooted tree with (n) nodes, where node (1) is the root. Initially, for every (2 \le i \le n) the parent is given as (p_i) (with (p_i < i)). You also start with (n) disjoint sets ({1},{2},\dots,{n}). For any two sets (A) and (B) that satisfy (A \cap B = \emptyset), you can perform an operation to obtain (A \cup B) at a cost of (|A|+|B|) (where (|A|) denotes the size of set (A)).

Then, there are (q) operations. Each operation is one of two types:

1. Query Operation: 0 a b. Let (S) be the set of nodes on the simple path from node (a) to node (b) in the tree. You must represent (S) as a union of already obtained disjoint sets (A_1, A_2, \dots, A_k) (i.e. (S = \cup_{i=1}^{k} A_i) with (A_i \cap A_j = \emptyset) for (i \neq j)). The cost to answer this query is (k).

2. Update Operation: 1 a b. Change the parent of node (a) to (b) (with (a > 1)). It is guaranteed that after the update the (n) nodes still form a tree (note that it is not guaranteed that (a > b)). In this operation you are allowed to generate new sets to help answer subsequent queries.

Let the total cost incurred during the entire program be (C_1), and let (C_2) be the maximum cost incurred in any single operation. Your score for each subtask will be determined by the values of (C_1) and (C_2).

Note: In this problem, you are not required to minimize the cost; you just need to correctly maintain the tree and answer the queries. A trivial solution is to output every node on the path as a singleton set (which is always valid since the initial (n) sets are available and remain disjoint).

inputFormat

The first line contains two integers (n) and (q) denoting the number of nodes and the number of operations respectively.
The second line contains (n-1) integers, where the (i^{{th}}) integer (for (i = 2,3,\dots,n)) is (p_i), the parent of node (i) ((p_i < i)).
Each of the following (q) lines represents an operation in one of the following forms:
• 0 a b : Query the tree for the path from node (a) to node (b).
• 1 a b : Update the tree by setting the parent of node (a) to (b) ((a > 1)).

outputFormat

For each query operation (i.e. lines starting with 0), first output an integer (k) which is the number of sets in your representation of the path. Then output (k) lines, each describing a set in the format:

m x1 x2 ... xm

where (m) is the size of the set (in the trivial solution, this will be 1) and (x1, x2, \dots, xm) are the nodes in that set. The order of nodes in the path should follow the order in which they appear on the unique simple path from (a) to (b).

sample

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

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