Im Labor von Professor JOI werden $N$ Arten von Mineralien erforscht. Von jeder Mineralart gibt es 2 Scheiben. Insgesamt gibt es $2N$ Scheiben, die von $1$ bis $2N$ nummeriert sind.

Eines Tages hat der Assistent Bitaro die Kiste mit den $2N$ Scheiben fallen lassen und weiß nun nicht mehr, welche Scheiben zur selben Mineralart gehören.

Das Labor besitzt ein Gerät, das anhand der von jedem Mineral absorbierten Wellenlänge die Anzahl der Mineralarten bestimmen kann, wenn einige Scheiben hineingelegt werden. Bitaro möchte aus den $2N$ Scheiben die $N$ Paare derselben Mineralart bestimmen. Zu Beginn befinden sich keine Scheiben im Gerät. Bitaro kann die folgenden Operationen ausführen:

• Eine Scheibe in das Gerät legen und erfahren, wie viele Mineralarten sich im Gerät befinden.
• Eine Scheibe aus dem Gerät entnehmen und erfahren, wie viele Mineralarten sich im Gerät befinden.

Damit Professor JOI nichts von Bitaros Missgeschick bemerkt, darf Bitaro diese Operationen insgesamt höchstens $1\,000\,000$ Mal ausführen.

Schreibe ein Programm, das bei gegebener Anzahl der Mineralarten mithilfe des Geräts alle Paare derselben Mineralart bestimmt.

Implementierungsdetails

Du musst eine Datei einreichen.

Die Datei heißt minerals.cpp. Sie soll die folgende Funktion implementieren. Das Programm soll minerals.h einbinden.

• void Solve(int N)

  Diese Funktion wird für jeden Testfall genau einmal aufgerufen.

  • Der Parameter N gibt $N$, die Anzahl der Mineralarten, an.

  Dein Programm kann die folgenden Funktionen aufrufen.

  • int Query(int x)

    Für die Scheibe mit dem angegebenen Index entnimmt diese Funktion die Scheibe aus dem Gerät, falls sie sich bereits darin befindet; andernfalls legt sie die Scheibe in das Gerät. Anschließend gibt sie die Anzahl der Mineralarten im Gerät zurück.

    • Mit dem Parameter x gibst du den Index $x$ der Scheibe an. Es muss $1 \le x \le 2N$ gelten. Andernfalls wird dein Programm mit Wrong Answer [1] bewertet.
    • Die Funktion Query darf nicht mehr als $1\,000\,000$ Mal aufgerufen werden. Andernfalls wird dein Programm mit Wrong Answer [2] bewertet.

  • void Answer(int a, int b)

    Mit dieser Funktion gibst du die Paare derselben Mineralart an.

    • Die Parameter a und b geben an, dass die $a$-te und die $b$-te Scheibe zur selben Mineralart gehören. Es muss $1 \le a \le 2N$ und $1 \le b \le 2N$ gelten. Andernfalls wird dein Programm mit Wrong Answer [3] bewertet. Kommt derselbe Wert insgesamt mehr als einmal in a oder b vor, wird dein Programm mit Wrong Answer [4] bewertet. Werden Scheiben unterschiedlicher Mineralarten angegeben, wird dein Programm mit Wrong Answer [5] bewertet.

  Die Funktion Answer muss genau $N$ Mal aufgerufen werden. Ist die Anzahl der Aufrufe von Answer am Ende der Ausführung von Solve ungleich $N$, wird dein Programm mit Wrong Answer [6] bewertet.

Wichtige Hinweise

• Dein Programm darf weitere Funktionen für den internen Gebrauch implementieren oder globale Variablen verwenden.
• Dein Programm darf weder die Standardeingabe noch die Standardausgabe verwenden. Es darf auf keine Weise mit anderen Dateien kommunizieren. Es darf jedoch Informationen zur Fehlersuche auf die Standardfehlerausgabe schreiben.

Kompilieren und Testen

Du kannst von der Webseite des Wettbewerbs ein Archiv herunterladen, das einen Beispiel-Grader zum Testen deines Programms enthält. Das Archiv enthält außerdem eine Beispielquelldatei für dein Programm.

Der Beispiel-Grader ist die Datei grader.cpp. Um dein Programm zu testen, lege grader.cpp, minerals.cpp und minerals.h in dasselbe Verzeichnis und führe den folgenden Befehl aus, um dein Programm zu kompilieren.

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

Bei erfolgreicher Kompilierung wird die ausführbare Datei grader erzeugt.

Beachte, dass sich der tatsächliche Grader vom Beispiel-Grader unterscheidet. Der Beispiel-Grader wird als einzelner Prozess ausgeführt, der Eingabedaten von der Standardeingabe liest und die Ergebnisse auf die Standardausgabe schreibt.

Eingabe für den Beispiel-Grader

Der Beispiel-Grader liest die folgenden Daten von der Standardeingabe.

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

$X_i$ und $Y_i$ ($1 \le i \le N$) geben an, dass die $X_i$-te und die $Y_i$-te Scheibe zur selben Mineralart gehören.

Ausgabe des Beispiel-Graders

Wenn das Programm erfolgreich beendet wird, schreibt der Beispiel-Grader die folgenden Informationen auf die Standardausgabe (Anführungszeichen dienen der Verdeutlichung).

• Wird dein Programm als korrekt bewertet, gibt er die Anzahl der Aufrufe der Funktion Query in der Form „Accepted: 100“ aus.
• Wird dein Programm mit einer falschen Antwort bewertet, gibt er deren Typ in der Form „Wrong Answer [1]“ aus.

Wird dein Programm mit mehreren Typen falscher Antworten bewertet, meldet der Beispiel-Grader nur einen davon.

Beschränkungen

Die Definition von $X_i$ und $Y_i$ findest du im Abschnitt „Eingabe für den Beispiel-Grader“.

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

Teilaufgaben

1. (6 Punkte) $N \le 100$.
2. (25 Punkte) $N \le 15\,000$, $1 \le X_i \le N$, $N+1 \le Y_i \le 2N$ ($1 \le i \le N$).
3. (9 Punkte) $N \le 15\,000$.
4. (30 Punkte) $N \le 38\,000$.
5. (5 Punkte) $N \le 39\,000$.
6. (5 Punkte) $N \le 40\,000$.
7. (5 Punkte) $N \le 41\,000$.
8. (5 Punkte) $N \le 42\,000$.
9. (10 Punkte) Keine weiteren Beschränkungen.

Beispiele

Hier sind eine Beispieleingabe für den Beispiel-Grader und die entsprechenden Funktionsaufrufe.

Eingabe 1

4
1 5
2 6
3 4
7 8

Beispielaufrufe