我们将针对多种生物的进化过程进行研究。除了最初的生物外，所有其他生物都是由已存在的生物进化而来的。此时，我们将已存在的生物定义为父生物，将新诞生的生物定义为子生物。
生物通过进化诞生的过程可以表示为以最初的生物为根的树结构，其中生物为节点，进化过程为连接父生物和子生物的边。例如，下图表示了 1 号生物进化出 2、3 号生物，2 号生物进化出 4、5、6 号生物，3 号生物进化出 7 号生物，6 号生物进化出 8、9 号生物的过程，并以 1 号生物为根构成了树结构。我们将这样的树称为进化树。
对于每个存在子进化体的生物，我们试图将其可能的进化方法中的一种分类为“主要进化”，其余的进化方法分类为“附加进化”。
这种分类方法的效率可以通过测量进化复杂度来获得。两个生物 A 和 B 之间的进化复杂度定义为在进化树中连接生物 A 和 B 的简单路径上所经过的附加进化的数量。进化树的进化复杂度定义为所有生物对之间进化复杂度的最大值。
随着进化复杂度的增加，分析两个生物之间的关联性变得更加困难，因此进化树的进化复杂度越低，效率就越高。因此，需要适当地将进化分类为主要进化和附加进化，以最小化进化树的进化复杂度。
研究将进行 $N + Q$ 天。研究的第一天仅发现了 1 号生物，每一天进行以下两种研究之一：
- 发现由已发现的生物进化而来的新生物。如果已发现的生物数量为 $T$，则该生物被命名为 $T + 1$ 号生物。此研究进行 $N$ 次。
- 对于某个生物，分析从该生物开始经过 0 次或多次进化而诞生的生物。对于以该生物为根构成的进化树，需要求出该进化树进化复杂度的最小值。请注意，每次分析都是独立的，且在此分析中分类的方法不会影响后续的分析。此研究进行 $Q$ 次。
请编写一个程序来执行该研究计划。
实现细节
你需要实现以下三个函数：
void init()- 该函数在
observation函数和analyze函数被调用之前仅被调用一次。
void observation(int P)- 对于作为参数给出的整数 $P$ 和当前已发现的生物数量 $T$，该函数意味着发现了由 $P$ 号生物进化而来的新的 $T + 1$ 号生物。
int analyze(int R)- 对于作为参数给出的整数 $R$，该函数意味着分析从 $R$ 号生物开始经过 0 次或多次进化而诞生的生物。
- 该函数应返回以 $R$ 号生物为根构成的进化树的进化复杂度的最小值。
提交的源代码的任何部分都不应执行输入输出函数。
数据范围
- $1 \le N \le 500\,000$
- $1 \le Q \le 500\,000$
子任务
- (7分) $N \le 15, Q \le 15$
- (11分) $N \le 3000, Q \le 15$
- (5分) $i$ 号生物的父生物是 $\lfloor \frac{i}{2} \rfloor$ 号生物 ($2 \le i \le N + 1$)
- (21分) 每个生物的子生物最多有 2 个。
- (15分) $N \le 3000, Q \le 3000$
- (41分) 无额外限制。
样例
输入格式 1
(input data)
输出格式 1
(output data)
说明
评测程序按顺序调用以下函数：
init()
observation(1)
observation(1)
observation(2)
observation(2)
observation(2)
observation(3)
analyze(1) = 2
observation(6)
analyze(2) = 2
observation(6)
analyze(6) = 1
analyze(1) = 2下图中的 4 个图分别表示每次 analyze 调用时，该分析所考虑的进化树及最优分类方法之一。主要进化以粗线标出。
Sample grader
Sample grader 按以下格式接收输入：
- Line 1: $N'$
- Line $1 + i$ ($1 \le i \le N'$): 若调用
observation函数则为1 P，若调用analyze函数则为2 R
其中 $N' = N + Q$。
Sample grader 输出以下内容：
- Line $i$ ($1 \le i \le Q$): 第 $i$ 次调用
analyze函数的返回值。
请注意，Sample grader 可能与实际评测时使用的 grader 不同。