В лаборатории профессора 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{matrix} N \\ X_1 & Y_1 \\ \vdots \\ X_N & Y_N \end{matrix} $$

$X_i$ и $Y_i$ ($1 \le i \le N$) означают, что образцы с номерами $X_i$ и $Y_i$ относятся к одному виду минерала.

Выходные данные примера проверяющей программы

При успешном завершении программы пример проверяющей программы записывает в стандартный вывод следующую информацию (кавычки приведены для ясности).

• Если ваша программа признана правильной, он выводит число вызовов функции Query в виде «Accepted: 100».
• Если ваша программа получает вердикт Wrong Answer, он выводит его тип в виде «Wrong Answer [1]».

Если ваша программа получает несколько типов вердикта Wrong Answer, пример проверяющей программы сообщает только один из них.

Ограничения

Определения $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

Пример вызовов