Лабораторія професора JOI досліджує $N$ видів мінералів. Кожен вид представлений двома зразками. Усього є $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{aligned} &N\\ &X_1\ Y_1\\ &\vdots\\ &X_N\ Y_N \end{aligned} $$

$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

Приклад викликів