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

有一天，助手 Bitaro 不小心弄掉了装有 $2N$ 片矿物的盒子，他不知道哪两片矿物属于同一种。

实验室拥有一种设备，可以通过测量每种矿物吸收的波长，在放入一些矿物切片时计算出其中包含的矿物种类数。Bitaro 打算从这 $2N$ 片矿物中确定 $N$ 对同种矿物。起初，设备中没有放入任何矿物。Bitaro 可以执行以下操作：

• 将一片矿物放入设备中，Bitaro 可以知道设备中有多少种矿物。
• 从设备中取出一片矿物，Bitaro 可以知道设备中有多少种矿物。

为了不让 JOI 教授发现 Bitaro 闯了祸，Bitaro 总共最多可以执行 $1\,000\,000$ 次这些操作。

请编写一个程序，在给定矿物种类数的情况下，使用该设备确定所有同种矿物的配对。

实现细节

你需要提交一个文件。 文件名应为 minerals.cpp。它应该实现以下函数。程序应包含 minerals.h。

• void Solve(int N) 该函数对每个测试用例仅调用一次。
  • 参数 $N$ 表示矿物的种类数。

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

• int Query(int 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]。

重要提示

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

编译与测试

你可以从竞赛网页下载包含样例评测程序的压缩包来测试你的程序。压缩包中还包含一个示例源文件。

样例评测程序文件名为 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，样例评测程序仅报告其中一种。

数据范围

请参考“样例评测程序的输入格式”部分了解 $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 \neq X_j$ ($1 \le i < j \le N$)
• $Y_i \neq Y_j$ ($1 \le i < j \le N$)
• $X_i \neq 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 X_i \le N, N + 1 \le Y_i \le 2N$ ($1 \le i \le N$)
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 分) 无附加限制

样例

样例输入 1

4
1 5
2 6
3 4
7 8

样例输出 1

Accepted: 10

说明

以下是样例评测程序的输入及对应的函数调用：