Minimizing Evolutionary Complexity

In this problem, you are given an evolving tree that models the evolution of various organisms. Initially, only organism 1 is known. Every new organism is generated by the evolution of an already‐discovered organism. For an organism with children, the evolutionary process is divided into two categories: a primary evolution and the remaining evolutions as secondary evolutions.

We define the evolutionary cost between two organisms (A) and (B) as the number of secondary evolutions along the unique path connecting (A) and (B) in the evolution tree (see the figure below):

The overall evolutionary complexity of the tree is defined as the maximum evolutionary cost among all pairs of organisms. However, since we can choose which child edge to mark as the primary evolution (at every organism with at least one child), we are allowed to assign these labels in order to minimize the evolutionary complexity of the tree.

For any organism (u) that has at least one child, suppose that if the children are (v_1,v_2,\dots,v_k) (with an already computed value (f(v)) for each child), we assign one edge as primary (with cost 0) and the others as secondary (each adds cost 1 when used). In particular, if we denote the value (f(u)) as the minimum possible maximum cost from (u) to any descendant (with an optimal assignment for (u)), then for (u) with no children we have [ f(u)=0, ] and for (u) with at least two children, letting (a_1\ge a_2\ge \cdots \ge a_k) be the sorted values (f(v_i)) of its children, an optimal choice is to select the child with (a_1) as primary. Then [ ; f(u)=\max\Bigl(a_1,, a_2+1\Bigr). ]

However, the evolutionary complexity of the subtree rooted at (u) (denoted by (D(u))) is defined as the maximum evolutionary cost over any two organisms in that subtree. In particular, if there are at least two children, two kinds of cross‐path costs may occur:

1. Between the primary branch and a secondary branch: cost = (a_1 + (a_2+1)).
2. Between two secondary branches: cost = ((a_2+1) + (a_3+1)=a_2+a_3+2) (if there are at least three children).

Then, with an optimal assignment at (u), we define [ D(u)=\max\Bigl( f(u),; \max_{v\in children(u)} D(v),; \text{if }|children(u)|\ge2:; \min\Bigl{a_1+(a_2+1),, (a_2+a_3+2)\Bigr}\Bigr). ]

You are to support two types of operations over a total of (N+Q) days:

• Observation: A new organism is discovered via the evolution of an existing organism. If there are currently (T) organisms, the new organism is numbered (T+1). The function call is

  void observation(int P);
  

  which indicates that a new organism is generated from organism (P).

• Analysis: Analyze the subtree (i.e. the evolution tree) rooted at a given organism. The function call is

  int analyze(int R);
  

  This function should return the minimum possible evolutionary complexity (D(R)) of the subtree rooted at (R) (with an optimal assignment of primary and secondary evolutions). Note that each analysis is independent and does not affect subsequent events.

Your task is to process (N+Q) operations. The input starts with two integers (N) and (Q) where (N) observations and (Q) analyses will occur. On each of the next (N+Q) lines, an operation is given in one of the following formats:

• "1 P" (observation): A new organism is evolved from organism (P).
• "2 R" (analyze): Output the minimal evolutionary complexity for the subtree rooted at organism (R).

You may assume that the operations are given in chronological order and that organism 1 exists at the beginning.

All formulas are given in (\LaTeX) format.

inputFormat

The first line contains two integers (N) and (Q) indicating the number of observation operations and analysis queries respectively. The following (N+Q) lines each represent an operation:

• For an observation, the line is: 1 P • For an analysis, the line is: 2 R

It is guaranteed that the operations are valid and given in chronological order. Initially, only organism 1 is known.

outputFormat

For each analysis query, output one line containing a single integer --- the minimum evolutionary complexity of the subtree rooted at the given organism.

sample

2 1
1 1
1 1
2 1

1

</p>