Il existe $N$ îles habitées par des castors, numérotées de $0$ à $N-1$. Ces îles sont reliées par $N-1$ ponts bidirectionnels. Il est possible de se déplacer entre deux îles quelconques en empruntant des ponts. Chaque île est directement reliée à au plus $18$ ponts. Chaque île est habitée par un castor.

Parfois, des castors se rassemblent sur une île pour tenir une réunion. Lorsque exactement trois castors se réunissent, ils se rassemblent sur l'île suivante :

L'île qui minimise le nombre total de ponts que les trois castors traversent pour se rassembler (une telle île existe et est unique).

Remarquez que cette île peut être celle où vit l'un des trois castors.

Vous souhaitez savoir comment les $N$ îles sont reliées par les ponts. Vous ne pouvez pas aller examiner directement les îles ; vous allez donc donner des instructions aux castors. Une instruction se déroule ainsi :

• Vous choisissez trois îles $u$, $v$ et $w$ ($0\le u\le N-1$, $0\le v\le N-1$, $0\le w\le N-1$, $u\ne v$, $u\ne w$, $v\ne w$), et demandez aux castors qui vivent sur ces îles de tenir une réunion.
• Vous pouvez ensuite observer l'île où les trois castors se rassemblent.

Vous voulez déterminer comment les îles sont reliées en donnant peu d'instructions.

Écrivez un programme qui, étant donné le nombre d'îles, communique avec les castors et détermine comment les îles sont reliées.

Détails d'implémentation

Vous devez soumettre un fichier.

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

• void Solve(int N)

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

• Le paramètre N représente $N$, le nombre d'îles.

Votre programme peut appeler les fonctions suivantes.

• int Query(int u, int v, int w)

Cette fonction renvoie, pour les indices des trois îles que vous indiquez, l'indice de l'île où les castors qui y vivent se rassemblent pour une réunion.

• Vous indiquez les indices $u$, $v$ et $w$ des trois îles par les paramètres u, v et w, respectivement. Ils doivent satisfaire $0\le u\le N-1$, $0\le v\le N-1$, $0\le w\le N-1$, $u\ne v$, $u\ne w$ et $v\ne w$. Sinon, votre programme est jugé Wrong Answer [1].

• La fonction Query ne doit pas être appelée plus de $100\,000$ fois. Sinon, votre programme est jugé Wrong Answer [2].

• void Bridge(int u, int v)

Cette fonction vous permet d'indiquer comment les îles sont reliées par les ponts.

• Les paramètres u et v indiquent que les îles $u$ et $v$ sont directement reliées par un pont.
• Si $0\le u<v\le N-1$ n'est pas vérifié, votre programme est jugé Wrong Answer [3].
• Si les îles $u$ et $v$ ne sont pas directement reliées par un pont, votre programme est jugé Wrong Answer [4].
• Si la fonction Bridge est appelée plusieurs fois avec les mêmes paramètres u et v, votre programme est jugé Wrong Answer [5].
• Puisqu'il existe $N-1$ ponts, la fonction Bridge doit être appelée exactement $N-1$ fois. Si, à la fin de l'exécution de Solve, le nombre d'appels à Bridge n'est pas égal à $N-1$, votre programme est jugé Wrong Answer [6].

Remarques importantes

• Votre programme peut implémenter d'autres fonctions pour son 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 aucun autre fichier, par quelque moyen que ce soit. 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. Cette archive contient également un exemple de fichier source de votre programme.

L'évaluateur d'exemple est le fichier grader.cpp. Pour tester votre programme, placez grader.cpp, meetings.cpp et meetings.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 meetings.cpp

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

Notez que l'évaluateur réel diffère de l'évaluateur d'exemple. L'évaluateur d'exemple 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{array}{l} N\\ A_0\ B_0\\ \vdots\\ A_{N-2}\ B_{N-2} \end{array} $$

$A_i$ et $B_i$ ($0\le i\le N-2$) indiquent que les îles $A_i$ et $B_i$ sont directement reliées par un pont.

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 à délimiter le texte).

• Si votre programme est jugé correct, il écrit le nombre d'appels à la fonction Query sous la forme « Accepted: 100 ».
• Si votre programme est jugé incorrect, il écrit le type d'erreur sous la forme « Wrong Answer [1] ».

Si votre programme relève de plusieurs types de réponse incorrecte, l'évaluateur d'exemple n'en signale qu'un seul.

Contraintes

Reportez-vous à la section « Entrée de l'évaluateur d'exemple » pour la définition de $A_i$ et $B_i$.

• $3\le N\le 2\,000$.
• $0\le A_i<B_i\le N-1$ ($0\le i\le N-2$).
• Il est possible de se déplacer entre deux îles quelconques en empruntant des ponts.
• Chaque île est directement reliée à au plus $18$ ponts.

Sous-tâches

1. (7 points) $N\le 7$.
2. (10 points) $N\le 50$.
3. (12 points) $N\le 300$.

4. (71 points) Aucune contrainte supplémentaire.

5. Pour les sous-tâches 1, 2 et 3, si votre programme est correct pour tous les cas de test d'une sous-tâche, vous obtenez la totalité des points de cette sous-tâche.

6. Pour la sous-tâche 4, si votre programme est correct pour tous les cas de test, votre score est calculé comme suit, où $X$ est le nombre maximal d'appels à Query pour un cas de test.

   • 49 points si $40\,000<X\le100\,000$, et
   • 71 points si $X\le40\,000$.

Exemples

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

Entrée 1

5
0 1
0 2
1 3
1 4

Appels d'exemple