Evolution

A research project is being conducted to study the evolution of species. In the beginning, there exists a single species, numbered as index \(1\).

The process of evolution may be expressed as a tree: At any point, an existing species may evolve to form a new species - said existing species is the new species' parent, and the new species is the existing species' child. Whenever this happens, we assign the new species the next integer index.

For example, in Figure 1 below, species \(1\) initially evolves to create species \(2\) and \(3\); after which species \(2\) evolves to create \(4\), \(5\), and \(6\); species \(3\) evolves to species \(7\); and finally species \(6\) forms species \(8\) and \(9\).

For any species with at least one child, we can assign to it a major branch leading to one of its children - the branches leading to its other children are then considered minor branches. Assigning a major branch to all eligible species defines a classification scheme for the evolutionary tree.

We can judge the efficiency of an evolutionary scheme by measuring its overall evolutionary complexity. The evolutionary complexity between two species A and B is defined as the number of minor branches on the shortest path between them; while the evolutionary complexity of an entire classification scheme is the maximum evolutionary complexity between any pair of its species.

Of course, schemes with a lower evolutionary complexity are easier to analyse - so we would like to minimise these evolutionary complexities.

The research project spans \(N + Q\) days. Before the first day, only species \(1\) exists. Then, on each day, one of two kinds of studies is conducted:

• \(1\) \(P\): Evolution is induced in species \(P\), creating a new species with the next available index as a direct child of \(P\). This study occurs \(N\) times.
• \(2\) \(R\): We seek to analyse the evolutionary subtree containing species \(R\) and its descendants. Output the minimum evolutionary complexity out of all possible classification schemes of this subtree. This study occurs \(Q\) times.

Your task is to determine the minimum complexity, for all studies of type \(2\).

Input format

The first line of input consists of a single integer \(N + Q\), the number of studies over the project.
\(N + Q\) lines of input follow. The \(i^{th}\) of these lines contains 2 integers, representing a valid study as described in the task description.

Output format

Output \(Q\) lines, one for each study of type \(2\) - each containing a single integer, the minimum evolutionary complexity of the required evolutionary subtree.

Limits

\(1 \leq N, Q \leq 500000\)
All \(P, R\) will refer to species that currently exist.

Subtask #	Score	Constraints
1	7	\(N, Q \leq 15\)
2	11	\(N \leq 3000\) \(Q \leq 15\)
3	5	The parent of species \(i\) is \(\left\lfloor\frac{i}{2}\right\rfloor\). \((2 \leq i \leq N + 1)\)
4	21	Each species will have no more than 2 direct children.
5	15	\(N, Q \leq 3000\)
6	41	No additional constraints

Samples

Sample Input 1	Sample Output 1
12 1 1 1 1 1 2 1 2 1 2 1 3 2 1 1 6 2 2 1 6 2 6 2 1	2 2 1 2

The four figures below demonstrate an optimal classification scheme for each type \(2\) study respectively, where major branches are bolded edges: