注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "evolution.h"。

题目描述

题目译自 2022년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사 T1 「진화」

我们正在研究多个生物体的进化过程。除了最初的生物体外，所有其他生物体都是通过现有生物体的进化而诞生的。我们将现有的生物体称为父生物体，新诞生的生物体称为子生物体。

生物体通过进化诞生的过程可以用一个树结构来表示，其中生物体是节点，进化过程是连接父生物体和子生物体的边。最初的生物体是树的根。例如，下图展示了一个进化树，其中 $1$ 号生物体进化出 $2$ 和 $3$ 号生物体，$2$ 号生物体进化出 $4$、$5$ 和 $6$ 号生物体，$3$ 号生物体进化出 $7$ 号生物体，$6$ 号生物体进化出 $8$ 和 $9$ 号生物体。

对于每个有子生物体的生物体，我们将可能的进化路径分为主要进化和次要进化。

这种分类方法的效率可以通过进化复杂度来衡量。两个生物体 $A$ 和 $B$ 之间的进化复杂度定义为进化树中连接 $A$ 和 $B$ 的路径上经过的次要进化的数量。进化树的进化复杂度是所有生物体对之间进化复杂度的最大值。

进化复杂度越高，分析两个生物体之间的关联性就越困难。因此，我们需要通过适当的分类方法将进化树的进化复杂度最小化。

研究将持续 $N+Q$ 天。第一天，我们只发现了 $1$ 号生物体。接下来的每一天，我们将进行以下两种研究之一：

• 发现一个新的生物体，该生物体是现有生物体进化而来的。如果现有生物体的数量为 $T$，那么这个新生物体将被命名为 $T+1$ 号生物体。这种研究将进行 $N$ 次。
• 分析一个生物体及其通过 $0$ 次或多次进化而诞生的所有生物体。我们需要计算以该生物体为根的进化树的最小进化复杂度。每次分析是独立的，不会影响后续的分析。这种研究将进行 $Q$ 次。

请编写一个程序来执行上述研究计划。

实现细节

你需要实现以下三个函数：

void init();

• 该函数在 observation 和 analyze 函数调用之前只会被调用一次。

void observation(int P);

• 该函数表示从编号为 $P$ 的生物体进化出一个新的生物体。当前发现的生物体数量为 $T$，新生物体编号为 $T+1$。

int analyze(int R);

• 该函数表示分析编号为 $R$ 的生物体及其通过 $0$ 次或多次进化而诞生的所有生物体。函数返回以 $R$ 号生物体为根的进化树的最小进化复杂度。

注意，提交的代码中不应包含任何输入输出操作。

样例

评测程序将按以下顺序调用函数：

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

下图展示了每次 analyze 调用时的进化树及其最佳分类方法之一。主要进化路径用粗线表示。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 5\cdot 10^5$
• $1 \leq Q \leq 5\cdot 10^5$

详细子任务附加限制及分值如下表所示。

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：$N'$
• 第 $1+i$ $(1 \leq i \leq N')$ 行：如果调用 observation 函数，则输入 1 P；如果调用 analyze 函数，则输入 2 R。$N' = N + Q$。

示例评测程序按以下格式输出：

• 第 $i$ $(1 \leq i \leq Q)$ 行：第 $i$ 次调用 analyze 函数的返回值

示例评测程序可能与实际评测程序不同。