3041 「JOISC 2019 Day4」矿物

题目译自 JOISC 2019 Day4 T3「鉱物 / Minerals」

JOI 教授的实验室正在研究 $N$ 种矿物。每种矿物有两个样本，一共有 $2N$ 个样本，编号为 $1\sim 2N$。

一天，助手 Bitaro 不小心弄掉了这个装有 $2N$ 个样本的箱子，他不知道哪两个样本是同一种矿物的样本了。

这个实验室有一台设备，可以通过测量每种矿物吸收光的波长，统计出插入这个设备的矿石种类数。Bitaro 决定利用这台设备给这 $2N$ 个样本中属于相同矿石种类的两两配对。起初，设备中没有矿石样本。Bitaro 可以如下操作： - 向设备中插入一个矿石样本，Bitaro 可以知道设备中有多少种矿石样本； - 从设备中拔出一个矿石样本，Bitaro 可以知道设备中有多少种矿石样本；

这样 JOI 教授就不会找 Bitaro 的麻烦了。Bitaro 总共可以操作最多 $10^6$ 次。

给出矿物种类数，写一个程序，利用这台设备给相同矿物种类样本配对。

实现细节

你需要提交一个文件，包含 minerals.h 并使用以下函数：

void Solve(int N)

对于每组数据，这个函数调用且仅调用一次。参数 N 代表 $N$，即矿物种类数。

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

int Query(int x)

对于你指定的样本编号，如果设备中有这个样本，则将其抽出，否则将其插入，返回设备中矿石样本种类数。 - 对于你通过参数 x 指定的样本编号 $x$，必须保证 $1\le x\le 2N$，否则程序将被判为 Wrong Answer [1]； - Query() 函数不能调用超过 $10^6$ 次，否则程序将被判为 Wrong Answer [2]；

void Answer(int a, int b)

利用这个函数，你可以回答相同矿石种类的矿石样本编号，意味着 $a$ 和 $b$ 号样本矿石种类相同。必须保证 $1\le a,b\le 2N$，否则程序将被判为 Wrong Answer [3]；如果重复回答同一对矿石，将被判为 Wrong Answer [4]，如果 $a$ 与 $b$ 并不属于同一种矿石，将被判为 Wrong Answer [5]。

Answer() 函数必须被调用 $N$ 次，否则程序将被判为 Wrong Answer [6]。

交互程序从标准输入中读入以下内容：

第一行一个正整数 $N$，表示矿石种类数；

接下来 $N$ 行，每行两个正整数 $X_i,Y_i$，表示编号为 $X_i$ 与 $Y_i$ 的矿石种类相同。

交互程序将向标准输出输出以下内容：

如果你的程序正确，将输出 Accepted: 100；

否则，将输出类似 Wrong Answer [1] 的内容。如果有多种错误，程序将只输出一个。

样例输入

4
1 5
2 6
3 4
7 8

样例交互过程

对于全部数据，$1\le N\le 4.3\times 10^4,1\le X_i,Y_i\le 2N$，保证每一个数对两两本质不同。

详细子任务附加条件及分值如下表：