Laboratorium profesora JOI prowadzi badania nad $N$ rodzajami minerałów. Istnieją po 2 płytki każdego rodzaju minerału. Łącznie jest $2N$ płytek, ponumerowanych od $1$ do $2N$.

Pewnego dnia asystent Bitaro upuścił pudełko zawierające $2N$ płytek i teraz nie wie, które płytki są tego samego rodzaju minerału.

Laboratorium posiada urządzenie, które potrafi zliczyć rodzaje minerałów wśród umieszczonych w nim płytek, mierząc długości fal pochłanianych przez każdy minerał. Bitaro zamierza wyznaczyć $N$ par płytek tego samego rodzaju minerału spośród $2N$ płytek. Początkowo w urządzeniu nie ma żadnych płytek. Bitaro może wykonywać następujące operacje:

• Po włożeniu jednej płytki do urządzenia Bitaro dowiaduje się, ile rodzajów minerałów znajduje się w urządzeniu.
• Po wyjęciu jednej płytki z urządzenia Bitaro dowiaduje się, ile rodzajów minerałów znajduje się w urządzeniu.

Aby profesor JOI nie odkrył, że Bitaro narobił kłopotów, Bitaro może wykonać te operacje łącznie co najwyżej $1\,000\,000$ razy.

Napisz program, który, mając daną liczbę rodzajów minerałów, za pomocą urządzenia wyznaczy wszystkie pary płytek tego samego rodzaju minerału.

Szczegóły implementacji

Należy przesłać jeden plik.

Plik musi nazywać się minerals.cpp. Powinien implementować poniższą funkcję. Program powinien dołączać minerals.h.

void Solve(int N)

Ta funkcja jest wywoływana dokładnie raz dla każdego przypadku testowego.

• Parametr N oznacza $N$, liczbę rodzajów minerałów.

Twój program może wywoływać następujące funkcje.

int Query(int x)

Dla wskazanego numeru płytki funkcja wyjmuje ją z urządzenia, jeśli już się w nim znajduje, a w przeciwnym razie wkłada ją do urządzenia. Następnie zwraca liczbę rodzajów minerałów w urządzeniu.

• Za pomocą parametru x wskazujesz numer $x$ płytki. Musi zachodzić $1 \le x \le 2N$. W przeciwnym razie program otrzyma werdykt Wrong Answer [1].
• Funkcji Query nie wolno wywołać więcej niż $1\,000\,000$ razy. W przeciwnym razie program otrzyma werdykt Wrong Answer [2].

void Answer(int a, int b)

Za pomocą tej funkcji podajesz pary płytek tego samego minerału.

• Parametry a i b oznaczają, że płytki o numerach $a$ i $b$ są tego samego rodzaju minerału. Muszą zachodzić $1 \le a \le 2N$ i $1 \le b \le 2N$. W przeciwnym razie program otrzyma werdykt Wrong Answer [3]. Jeśli ta sama wartość wystąpi więcej niż raz łącznie w parametrach a lub b, program otrzyma werdykt Wrong Answer [4]. Jeśli wskazane płytki są różnych rodzajów minerałów, program otrzyma werdykt Wrong Answer [5].

Funkcję Answer należy wywołać dokładnie $N$ razy. Jeśli w chwili zakończenia wykonywania funkcji Solve liczba wywołań funkcji Answer nie jest równa $N$, program otrzyma werdykt Wrong Answer [6].

Ważne uwagi

• Twój program może implementować inne funkcje do użytku wewnętrznego lub korzystać ze zmiennych globalnych.
• Twój program nie może korzystać ze standardowego wejścia ani standardowego wyjścia. Nie może w żaden sposób komunikować się z innymi plikami. Może jednak wypisywać informacje diagnostyczne na standardowe wyjście błędów.

Kompilacja i uruchamianie testów

Ze strony zawodów można pobrać archiwum zawierające przykładowy program oceniający, służący do testowania twojego programu. Archiwum zawiera również przykładowy plik źródłowy twojego programu.

Przykładowy program oceniający znajduje się w pliku grader.cpp. Aby przetestować swój program, umieść pliki grader.cpp, minerals.cpp i minerals.h w tym samym katalogu, a następnie uruchom poniższe polecenie, aby skompilować programy.

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

Po pomyślnej kompilacji powstaje plik wykonywalny grader.

Pamiętaj, że rzeczywisty program oceniający różni się od przykładowego. Przykładowy program oceniający działa jako pojedynczy proces, który czyta dane ze standardowego wejścia i wypisuje wyniki na standardowe wyjście.

Wejście przykładowego programu oceniającego

Przykładowy program oceniający czyta ze standardowego wejścia następujące dane.

$$ \begin{gathered} N\\ X_1\ Y_1\\ \vdots\\ X_N\ Y_N \end{gathered} $$

$X_i$ i $Y_i$ ($1 \le i \le N$) oznaczają, że płytki o numerach $X_i$ i $Y_i$ są tego samego rodzaju minerału.

Wyjście przykładowego programu oceniającego

Gdy program zakończy działanie pomyślnie, przykładowy program oceniający wypisuje na standardowe wyjście następujące informacje (cudzysłowy służą wyłącznie czytelności).

• Jeśli twój program zostanie uznany za poprawny, wypisuje liczbę wywołań funkcji Query, na przykład „Accepted: 100”.
• Jeśli twój program otrzyma werdykt błędnej odpowiedzi, wypisuje jego rodzaj, na przykład „Wrong Answer [1]”.

Jeśli twój program spełnia warunki kilku rodzajów błędnej odpowiedzi, przykładowy program oceniający zgłasza tylko jeden z nich.

Ograniczenia

Definicje $X_i$ i $Y_i$ znajdują się w sekcji „Wejście przykładowego programu oceniającego”.

• $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$).

Podzadania

1. (6 punktów) $N \le 100$.
2. (25 punktów) $N \le 15\,000$, $1 \le X_i \le N$, $N+1 \le Y_i \le 2N$ ($1 \le i \le N$).
3. (9 punktów) $N \le 15\,000$.
4. (30 punktów) $N \le 38\,000$.
5. (5 punktów) $N \le 39\,000$.
6. (5 punktów) $N \le 40\,000$.
7. (5 punktów) $N \le 41\,000$.
8. (5 punktów) $N \le 42\,000$.
9. (10 punktów) Brak dodatkowych ograniczeń.

Przykład

Oto przykładowe wejście przykładowego programu oceniającego i odpowiadające mu wywołania funkcji.

Wejście 1

4
1 5
2 6
3 4
7 8

Przykładowe wywołania