Laboratorium Profesor JOI sedang meneliti $N$ jenis mineral. Terdapat $2$ irisan dari setiap jenis mineral. Seluruhnya ada $2N$ irisan, yang diberi nomor dari $1$ hingga $2N$.

Suatu hari, asisten Bitaro menjatuhkan kotak yang berisi $2N$ irisan tersebut, sehingga ia tidak tahu lagi irisan mana yang berasal dari jenis mineral yang sama.

Laboratorium tersebut memiliki sebuah alat yang dapat menghitung banyaknya jenis mineral ketika beberapa irisan dimasukkan ke dalamnya, dengan mengukur panjang gelombang yang diserap oleh setiap mineral. Bitaro akan menentukan $N$ pasangan irisan dari jenis mineral yang sama di antara $2N$ irisan tersebut. Pada awalnya, tidak ada irisan di dalam alat. Bitaro dapat melakukan operasi berikut:

• Memasukkan satu irisan ke dalam alat, lalu mengetahui banyaknya jenis mineral di dalam alat.
• Mengeluarkan satu irisan dari alat, lalu mengetahui banyaknya jenis mineral di dalam alat.

Agar Profesor JOI tidak mengetahui bahwa Bitaro telah menimbulkan masalah, Bitaro hanya boleh melakukan operasi-operasi tersebut paling banyak $1\,000\,000$ kali secara keseluruhan.

Tulislah program yang, diberikan banyaknya jenis mineral, menggunakan alat tersebut untuk menentukan semua pasangan irisan dari jenis mineral yang sama.

Detail Implementasi

Anda harus mengumpulkan satu berkas.

Nama berkas tersebut adalah minerals.cpp. Berkas ini harus mengimplementasikan fungsi berikut. Program harus menyertakan minerals.h.

• void Solve(int N)

Fungsi ini dipanggil tepat satu kali untuk setiap kasus uji.

• Parameter N menyatakan $N$, yaitu banyaknya jenis mineral.

Program Anda dapat memanggil fungsi-fungsi berikut.

• int Query(int x)

Untuk nomor irisan yang Anda tentukan, fungsi ini mengeluarkan irisan tersebut dari alat jika irisan itu sudah berada di dalam alat, atau memasukkannya ke dalam alat jika belum. Kemudian, fungsi ini mengembalikan banyaknya jenis mineral di dalam alat.

• Anda menentukan nomor irisan $x$ melalui parameter x. Nilainya harus memenuhi $1\le x\le 2N$. Jika tidak, program Anda dinilai Wrong Answer [1].

• Fungsi Query tidak boleh dipanggil lebih dari $1\,000\,000$ kali. Jika dilanggar, program Anda dinilai Wrong Answer [2].

• void Answer(int a, int b)

Dengan fungsi ini, Anda melaporkan pasangan irisan dari mineral yang sama.

• Parameter a dan b menyatakan bahwa irisan ke-$a$ dan irisan ke-$b$ berasal dari jenis mineral yang sama. Nilainya harus memenuhi $1\le a\le 2N$ dan $1\le b\le 2N$. Jika tidak, program Anda dinilai Wrong Answer [3]. Jika suatu nilai muncul lebih dari sekali dalam keseluruhan parameter a atau b, program Anda dinilai Wrong Answer [4]. Jika irisan yang ditentukan berasal dari jenis mineral yang berbeda, program Anda dinilai Wrong Answer [5].

Fungsi Answer harus dipanggil tepat $N$ kali. Jika banyaknya pemanggilan fungsi Answer bukan $N$ ketika eksekusi fungsi Solve berakhir, program Anda dinilai Wrong Answer [6].

Catatan Penting

• Program Anda boleh mengimplementasikan fungsi lain untuk penggunaan internal atau menggunakan variabel global.
• Program Anda tidak boleh menggunakan masukan standar maupun keluaran standar. Program Anda tidak boleh berkomunikasi dengan berkas lain melalui cara apa pun. Namun, program Anda boleh menuliskan informasi debug ke keluaran galat standar.

Kompilasi dan Pengujian

Anda dapat mengunduh sebuah berkas arsip dari halaman web kontes yang berisi grader contoh untuk menguji program Anda. Arsip tersebut juga berisi contoh berkas kode sumber program Anda.

Grader contoh adalah berkas grader.cpp. Untuk menguji program Anda, letakkan grader.cpp, minerals.cpp, dan minerals.h dalam direktori yang sama, lalu jalankan perintah berikut untuk mengompilasi program Anda.

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

Jika kompilasi berhasil, berkas executable grader akan dihasilkan.

Perhatikan bahwa grader sebenarnya berbeda dari grader contoh. Grader contoh akan dijalankan sebagai satu proses yang membaca data masukan dari masukan standar dan menuliskan hasil ke keluaran standar.

Masukan untuk Grader Contoh

Grader contoh membaca data berikut dari masukan standar.

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

$X_i$ dan $Y_i$ ($1\le i\le N$) menyatakan bahwa irisan ke-$X_i$ dan irisan ke-$Y_i$ berasal dari jenis mineral yang sama.

Keluaran Grader Contoh

Ketika program berakhir dengan sukses, grader contoh menuliskan informasi berikut ke keluaran standar (tanda kutip digunakan untuk memperjelas).

• Jika program Anda dianggap benar, grader menuliskan banyaknya pemanggilan fungsi Query, seperti Accepted: 100.
• Jika program Anda dinilai Wrong Answer, grader menuliskan jenisnya, seperti Wrong Answer [1].

Jika program Anda dinilai mengalami beberapa jenis Wrong Answer, grader contoh hanya melaporkan salah satunya.

Batasan

Lihat bagian “Masukan untuk Grader Contoh” untuk definisi $X_i$ dan $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$).

Subsoal

1. (6 poin) $N\le 100$.
2. (25 poin) $N\le 15\,000$, $1\le X_i\le N$, $N+1\le Y_i\le 2N$ ($1\le i\le N$).
3. (9 poin) $N\le 15\,000$.
4. (30 poin) $N\le 38\,000$.
5. (5 poin) $N\le 39\,000$.
6. (5 poin) $N\le 40\,000$.
7. (5 poin) $N\le 41\,000$.
8. (5 poin) $N\le 42\,000$.
9. (10 poin) Tidak ada batasan tambahan.

Contoh Komunikasi

Berikut adalah contoh masukan untuk grader contoh beserta pemanggilan fungsi yang bersesuaian.

Masukan 1

4
1 5
2 6
3 4
7 8

Contoh Pemanggilan