JOI 教授嘅實驗室正研究 $N$ 種礦物。每種礦物都有 2 塊切片，合共有 $2N$ 塊，編號由 $1$ 至 $2N$。

有一日，助手 Bitaro 跌咗個裝住呢 $2N$ 塊切片嘅盒，結果佢唔知邊兩塊切片係同一種礦物。

實驗室有部裝置，可以量度各種礦物吸收嘅波長，計出放咗入去嘅切片包含幾多種礦物。Bitaro 打算喺呢 $2N$ 塊切片之中，搵出屬於同一種礦物嘅 $N$ 對切片。最初裝置入面冇切片。Bitaro 可以進行以下操作：

• 將一塊切片放入裝置，然後得知裝置入面有幾多種礦物。
• 將一塊切片由裝置取出，然後得知裝置入面有幾多種礦物。

為咗唔畀 JOI 教授發現自己闖咗禍，Bitaro 總共最多只可以進行 $1\,000\,000$ 次呢啲操作。

請寫一個程式，根據礦物種類嘅數目，利用裝置搵出所有屬於同一種礦物嘅切片配對。

實作細節

你需要提交一個檔案。

檔案名稱係 minerals.cpp，入面要實作以下函式。程式要包含 minerals.h。

void Solve(int N)

每個測試案例都會呼叫呢個函式恰好一次。

• 參數 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]。

重要事項

• 你嘅程式可以實作其他函式作內部用途，亦可以用全域變數。
• 你嘅程式唔可以用標準輸入同標準輸出，亦唔可以透過任何方法同其他檔案通訊。不過，你可以將除錯資訊輸出去標準錯誤。

編譯及測試

你可以喺比賽網頁下載一個壓縮檔，入面有用嚟測試程式嘅範例評測器，亦有你要寫嘅程式嘅範例原始碼。

範例評測器係 grader.cpp。要測試程式，請將 grader.cpp、minerals.cpp 同 minerals.h 放喺同一個目錄，再執行以下指令編譯程式。

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

編譯成功之後，就會產生可執行檔 grader。

請留意，實際評測器同範例評測器唔同。範例評測器會以單一程序執行，從標準輸入讀取資料，並將結果寫去標準輸出。

範例評測器嘅輸入格式

範例評測器會從標準輸入讀取以下資料。

$$ \begin{array}{ll} N\\ X_1&Y_1\\ \vdots\\ X_N&Y_N \end{array} $$

$X_i$ 同 $Y_i$（$1 \le i \le N$）表示第 $X_i$ 塊同第 $Y_i$ 塊切片屬於同一種礦物。

範例評測器嘅輸出格式

當程式成功結束，範例評測器會將以下資訊寫去標準輸出（為咗清楚起見，以下用引號標示）。

• 如果你嘅程式被判為正確，就會輸出呼叫 Query 嘅次數，格式例如「Accepted: 100」。
• 如果你嘅程式被判為答案錯誤，就會輸出錯誤類型，格式例如「Wrong Answer [1]」。

如果你嘅程式符合多種答案錯誤類型，範例評測器只會報告其中一種。

資料範圍

$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 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

函式呼叫範例