题目背景

在洛谷上提交本题，需要定义函数 int Query(int x);、void Answer(int a, int b); 而非引用头文件 minerals.h。

题目描述

JOI 教授的实验室正在研究 $N$ 种矿物。每种矿物有 2 片样本，总共有 $2N$ 片样本，编号从 $1$ 到 $2N$。

某天，助手 Bitaro 不慎将装有这 $2N$ 片样本的盒子打翻，他已无法分辨哪两片样本属于同一种矿物。

实验室拥有一种设备，可通过测量每种矿物吸收的波长，来统计设备内当前包含的矿物种类数量。Bitaro 的任务是从 $2N$ 片样本中找出所有 $N$ 对同种矿物。初始时，设备内没有放入任何样本。Bitaro 可执行以下操作：

• 将一片样本插入设备中，Bitaro 会得知设备内当前包含的矿物种类数量。
• 从设备中取出一片样本，Bitaro 会得知设备内当前包含的矿物种类数量。

为避免被 JOI 教授发现 Bitaro 惹出麻烦，他总共最多只能执行 $1\,000\,000$ 次操作。

请编写一个程序，给定矿物种类数 $N$，利用该设备，找出所有同种矿物的配对。

实现细节

程序应实现以下函数：

• void Solve(int N)
  此函数在每个测试用例中恰好被调用一次。
  • 参数 $N$ 表示矿物种类的数量。

你的程序可以调用以下函数：

• int Query(int x)
  对于你指定的样本编号 $x$，若该样本已在设备中，则将其取出；否则将其插入设备中。然后返回设备中当前包含的矿物种类数量。
  • 你通过参数 $x$ 指定样本编号，必须满足 $1 \le x \le 2N$。否则，你的程序将被判定为 Wrong Answer [1]。
  • 函数 Query 的调用次数不得超过 $1\,000\,000$ 次。否则，你的程序将被判定为 Wrong Answer [2]。
• void Answer(int a, int b)
  使用此函数，你将输出同种矿物的配对。
  • 参数 $a$ 和 $b$ 表示第 $a$ 片样本与第 $b$ 片样本属于同一种矿物。它们必须满足 $1 \le a \le 2N$ 且 $1 \le b \le 2N$。否则，你的程序将被判定为 Wrong Answer [3]。
  • 若在 $a$ 或 $b$ 中，同一数值出现超过一次，你的程序将被判定为 Wrong Answer [4]。
  • 若指定的样本属于不同种类的矿物，你的程序将被判定为 Wrong Answer [5]。

函数 Answer 必须恰好被调用 $N$ 次。若在函数 Solve 执行结束时，对 Answer 的调用次数不等于 $N$，你的程序将被判定为 Wrong Answer [6]。

重要提示

• 你的程序可以为内部使用实现其他函数，或使用全局变量。
• 你的程序不得使用标准输入和标准输出，也不得通过任何方式与其他文件通信。但你的程序可以向 stderr 输出调试信息。

编译与测试运行

你可以从竞赛网页下载一个归档文件，其中包含用于测试你程序的样例评测器。该归档文件还包含你程序的样例源代码文件。

样例评测器是文件 grader.cpp。为测试你的程序，请将 grader.cpp、minerals.cpp 和 minerals.h 放在同一目录下，并运行以下命令编译你的程序：

g++ -std=gnu++14 -O2 -o grader grader.cpp minerals.cpp

当编译成功后，将生成可执行文件 grader。

请注意，实际评测器与样例评测器不同。样例评测器将以单进程方式运行，从标准输入读取输入数据，并将结果写入标准输出。

输入格式

样例评测器从标准输入读取以下数据：

$N$

$X_1\ Y_1$

$\vdots$

$X_N\ Y_N$

其中，$X_i$ 和 $Y_i$（$1 \le i \le N$）表示第 $X_i$ 片样本与第 $Y_i$ 片样本属于同一种矿物。

输出格式

当程序成功终止时，样例评测器将以下信息写入标准输出（引号仅用于清晰说明）：

• 若你的程序被判定为正确，它将输出调用函数 Query 的次数，格式为 “Accepted: 100”。
• 若你的程序被判定为 Wrong Answer，它将输出其类型，格式为 “Wrong Answer [1]”。

若你的程序被判定为多种类型的 Wrong Answer，样例评测器仅报告其中一种。

4
1 5
2 6
3 4
7 8

提示

样例 1 解释

调用		返回值
Solve(4)
	Query(1)	1
	Query(2)	2
	Query(5)
	Query(2)	1
	Answer(3, 4)	（无）
	Answer(5, 1)
	Answer(8, 7)
	Answer(2, 6)

数据范围

关于 $X_i$ 和 $Y_i$ 的定义，请参阅“样例评测器的输入”部分。

• $1 \le N \le 43\,000$。
• $1 \le X_i \le 2N$（$1 \le i \le N$）。
• $1 \le Y_i \le 2N$（$1 \le i \le N$）。
• $X_i \ne X_j$（$1 \le i < j \le N$）。
• $Y_i \ne Y_j$（$1 \le i < j \le N$）。
• $X_i \ne Y_j$（$1 \le i \le N$，$1 \le j \le N$）。

子任务

1. （6 分）$N \le 100$。
2. （25 分）$N \le 15\,000$，且对所有 $1 \le i \le N$，满足 $1 \le X_i \le N$，$N + 1 \le Y_i \le 2N$。
3. （9 分）$N \le 15\,000$。
4. （30 分）$N \le 38\,000$。
5. （5 分）$N \le 39\,000$。
6. （5 分）$N \le 40\,000$。
7. （5 分）$N \le 41\,000$。
8. （5 分）$N \le 42\,000$。
9. （10 分）无额外约束。