题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码：

#include<bits/stdc++.h>
void init();
int analyze(int R);
void observation(int P);

题目译自 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$ 号生物体为根的进化树的最小进化复杂度。

输入格式

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

• 第 $1$ 行：$N'$

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

• $N' = N + Q$。

输出格式

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

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

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

10
1 1
1 1
2 1
1 2
1 2
1 3
2 1
1 3
1 4
2 1

1
2
3

提示

样例解释 #1

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

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$	$7$	$N \leq 15,Q \leq 15$
$2$	$11$	$N \leq 3000,Q \leq 15$
$3$	$5$	第 $i (2 \leq i \leq N+1)$ 号生物体的父生物体是 $\left\lfloor\frac{i}{2}\right\rfloor$ 号生物体
$4$	$21$	每个生物体最多有 $2$ 个子生物体
$5$	$15$	$N \leq 3000,Q \leq 3000$
$6$	$41$	无附加限制