Le laboratoire du professeur JOI étudie $N$ sortes de minéraux. Il possède 2 lamelles de chaque sorte de minéral, soit $2N$ lamelles au total, numérotées de $1$ à $2N$.

Un jour, l'assistant Bitaro a fait tomber la boîte contenant les $2N$ lamelles et ne sait plus quelles lamelles sont de la même sorte de minéral.

Le laboratoire possède un appareil capable de compter le nombre de sortes de minéraux parmi les lamelles qu'on y insère, en mesurant la longueur d'onde absorbée par chaque minéral. Bitaro va déterminer les $N$ paires de lamelles de la même sorte parmi les $2N$ lamelles. Au départ, aucune lamelle ne se trouve dans l'appareil. Bitaro peut effectuer les opérations suivantes :

• Insérer une lamelle dans l'appareil, puis connaître le nombre de sortes de minéraux présentes dans l'appareil.
• Retirer une lamelle de l'appareil, puis connaître le nombre de sortes de minéraux présentes dans l'appareil.

Pour que le professeur JOI ne découvre pas les ennuis causés par Bitaro, celui-ci peut effectuer ces opérations au plus $1\,000\,000$ fois au total.

Écrivez un programme qui, connaissant le nombre de sortes de minéraux, utilise l'appareil pour déterminer toutes les paires de lamelles de la même sorte de minéral.

Détails d'implémentation

Vous devez soumettre un fichier.

Ce fichier s'appelle minerals.cpp. Il doit implémenter la fonction suivante. Le programme doit inclure minerals.h.

• void Solve(int N)

Cette fonction est appelée exactement une fois par cas de test.

• Le paramètre N représente $N$, le nombre de sortes de minéraux.

Votre programme peut appeler les fonctions suivantes.

• int Query(int x)

Pour l'indice de lamelle que vous spécifiez, cette fonction retire la lamelle de l'appareil si elle s'y trouve déjà, ou l'y insère dans le cas contraire. Elle renvoie ensuite le nombre de sortes de minéraux présentes dans l'appareil.

• Vous spécifiez l'indice $x$ de la lamelle au moyen du paramètre x. Il doit satisfaire $1\le x\le 2N$. Sinon, votre programme reçoit le verdict Wrong Answer [1].

• La fonction Query ne doit pas être appelée plus de $1\,000\,000$ fois. Sinon, votre programme reçoit le verdict Wrong Answer [2].

• void Answer(int a, int b)

Cette fonction vous permet d'indiquer les paires de lamelles du même minéral.

• Les paramètres a et b indiquent que la $a$-ième lamelle et la $b$-ième lamelle sont de la même sorte de minéral. Ils doivent satisfaire $1\le a\le 2N$ et $1\le b\le 2N$. Sinon, votre programme reçoit le verdict Wrong Answer [3]. Si une même valeur apparaît plus d'une fois parmi l'ensemble des valeurs de a et de b, votre programme reçoit le verdict Wrong Answer [4]. Si vous spécifiez des lamelles de sortes de minéraux différentes, votre programme reçoit le verdict Wrong Answer [5].

La fonction Answer doit être appelée exactement $N$ fois. Si le nombre d'appels à Answer n'est pas $N$ à la fin de l'exécution de Solve, votre programme reçoit le verdict Wrong Answer [6].

Avis importants

• Votre programme peut implémenter d'autres fonctions à usage interne ou utiliser des variables globales.
• Votre programme ne doit utiliser ni l'entrée standard ni la sortie standard. Il ne doit communiquer avec d'autres fichiers par aucun moyen. Il peut toutefois écrire des informations de débogage sur la sortie d'erreur standard.

Compilation et exécution de test

Vous pouvez télécharger depuis la page web du concours une archive contenant l'évaluateur d'exemple pour tester votre programme. L'archive contient également un fichier source d'exemple pour votre programme.

L'évaluateur d'exemple est le fichier grader.cpp. Pour tester votre programme, placez grader.cpp, minerals.cpp et minerals.h dans le même répertoire, puis exécutez la commande suivante pour compiler vos programmes.

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

Si la compilation réussit, le fichier exécutable grader est créé.

Notez que l'évaluateur réel est différent de l'évaluateur d'exemple. Ce dernier s'exécute dans un seul processus, qui lit les données sur l'entrée standard et écrit les résultats sur la sortie standard.

Entrée de l'évaluateur d'exemple

L'évaluateur d'exemple lit les données suivantes sur l'entrée standard.

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

$X_i$ et $Y_i$ ($1\le i\le N$) indiquent que la $X_i$-ième lamelle et la $Y_i$-ième lamelle sont de la même sorte de minéral.

Sortie de l'évaluateur d'exemple

Lorsque le programme se termine normalement, l'évaluateur d'exemple écrit les informations suivantes sur la sortie standard (les guillemets servent à clarifier la présentation).

• Si votre programme est considéré comme correct, il écrit le nombre d'appels à la fonction Query, par exemple Accepted: 100.
• Si votre programme reçoit le verdict Wrong Answer, il en écrit le type, par exemple Wrong Answer [1].

Si votre programme reçoit plusieurs types de Wrong Answer, l'évaluateur d'exemple n'en signale qu'un seul.

Contraintes

Consultez la section « Entrée de l'évaluateur d'exemple » pour la définition de $X_i$ et $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$).

Sous-tâches

1. (6 points) $N\le 100$.
2. (25 points) $N\le 15\,000$, $1\le X_i\le N$, $N+1\le Y_i\le 2N$ ($1\le i\le N$).
3. (9 points) $N\le 15\,000$.
4. (30 points) $N\le 38\,000$.
5. (5 points) $N\le 39\,000$.
6. (5 points) $N\le 40\,000$.
7. (5 points) $N\le 41\,000$.
8. (5 points) $N\le 42\,000$.
9. (10 points) Aucune contrainte supplémentaire.

Exemples

Voici un exemple d'entrée pour l'évaluateur d'exemple et les appels de fonctions correspondants.

Entrée 1

4
1 5
2 6
3 4
7 8

Appels d'exemple