JOI 教授的實驗室正在研究 $N$ 種礦物。每種礦物都有 2 個切片，總共有 $2N$ 個切片，編號為 $1$ 到 $2N$。

有一天，助手 Bitaro 不小心摔落了裝著這 $2N$ 個切片的盒子，因此他不知道哪些切片屬於同一種礦物。

實驗室擁有一臺裝置，將一些切片放入其中後，它可以藉由測量各種礦物吸收的波長，計算裝置內的礦物種類數。Bitaro 打算從這 $2N$ 個切片中找出屬於同種礦物的 $N$ 對切片。最初，裝置內沒有任何切片。Bitaro 可以進行下列操作：

• 將一個切片放入裝置，得知裝置內有多少種礦物。
• 從裝置中取出一個切片，得知裝置內有多少種礦物。

為了不讓 JOI 教授發現 Bitaro 闖了禍，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{gathered} N\\ X_1\ Y_1\\ \vdots\\ X_N\ Y_N \end{gathered} $$

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

範例評測程式的輸出格式

當程式順利結束時，範例評測程式會將下列資訊寫入標準輸出（引號僅用於使說明清楚）。

• 如果你的程式被判定為正確，會以 Accepted: 100 這樣的形式輸出 Query 函式的呼叫次數。
• 如果你的程式被判定為答案錯誤，會以 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

範例呼叫