Ce problème est interactif.

En cette fête empreinte de doux parfums sucrés, la préparation du dessert final — le lait à double peau — rencontre une dernière difficulté.

Dessert le plus apprécié de la boutique, un lait à double peau parfait exige une fusion parfaite du gâteau de la couche supérieure et du pudding de la couche inférieure. Dans ce merveilleux royaume des puces, les énergies de ces deux couches de dessert s'entremêlent et se cachent dans un réseau complexe de villes.

Les deux maîtres pâtissiers expérimentés de la boutique — dacake8 et dapudding8 — ont décidé de vous mettre à l'épreuve. Ils ont caché respectivement les gâteaux et les puddings sur les routes entre les villes. Ce n'est qu'en les interrogeant et en identifiant précisément une ville reliée à la boutique principale où vous vous trouvez (la ville $1$) par une route contenant un dessert que vous pourrez réussir ce lait à double peau qui clôt le repas !

Il y a $n$ villes, et chaque paire de villes est reliée par une route. Il y a $n-1$ morceaux de gâteau ; le $i$-ème se trouve sur la route reliant les villes $u_{i,1}$ et $v_{i,1}$. Il y a $n-1$ portions de pudding ; la $i$-ème se trouve sur la route reliant les villes $u_{i,2}$ et $v_{i,2}$. Les routes contenant du gâteau et celles contenant du pudding forment respectivement deux arbres.

Au départ, vous ne connaissez pas les positions exactes des gâteaux et des puddings. Vous pouvez adresser à dacake8 et dapudding8 au plus $\min(1000,\frac{n\times(n-1)}{2})$ requêtes :

• Vous interrogez dacake8 et dapudding8 sur les villes $u$ et $v$. Initialement, le multiensemble $S$ est vide.
  • dacake8 part de la ville $u$, suit le chemin dont les routes contiennent du gâteau jusqu'à la ville $v$ et ajoute au multiensemble $S$ les numéros des villes traversées.
  • dapudding8 part de la ville $u$, suit le chemin dont les routes contiennent du pudding jusqu'à la ville $v$ et ajoute au multiensemble $S$ les numéros des villes traversées.
• La bibliothèque d'interaction renvoie le multiensemble $S$.

Vous vous trouvez dans la ville $1$. Une fois les requêtes terminées, vous devez donner une ville $u$ telle que la route reliant les villes $1$ et $u$ contienne un type de dessert.

dacake8 et dapudding8 ne souhaitent pas vous compliquer la tâche : ils garantissent que les positions des gâteaux et des puddings sont fixées avant les requêtes. Autrement dit, la bibliothèque d'interaction est non adaptative.

Détails d'implémentation

Vous n'avez pas besoin d'implémenter la fonction main, et vous ne devez pas le faire.

Vous devez inclure le fichier d'en-tête milk.h dans le fichier source milk.cpp et implémenter les deux fonctions suivantes :

void init(int c, int t);

• $c,t$ désignent respectivement le numéro de la sous-tâche et le nombre de cas de test. $id=0$ indique que le test est un exemple.
• Pour chaque test, cette fonction est appelée exactement une fois par la bibliothèque d'interaction au démarrage du programme.

int find(int c, int n);

• $c,n$ désignent respectivement le numéro de la sous-tâche et le nombre de villes.
• Cette fonction doit renvoyer un entier strictement positif $u$, indiquant une ville $u$ telle que la route reliant les villes $1$ et $u$ contienne un type de dessert.
• Pour chaque test, cette fonction est appelée exactement $t$ fois par la bibliothèque d'interaction.

Vous pouvez effectuer une requête en appelant la fonction suivante :

std::vector<int>query(int u, int v);

• $u,v$ indiquent les deux villes $u$ et $v$ choisies.
• Vous devez garantir que $1\le u,v\le n$ et $u\ne v$.
• Cette fonction renvoie le multiensemble $S$, dont la signification est décrite dans l'énoncé.
• Si la taille du multiensemble $S$ est $m$, alors $1\le S_i\le n$ et $S_0\le S_1\le \ldots \le S_{m-1}$.
• Vous devez veiller à ce que le nombre d'appels à cette fonction ne dépasse pas $1000$ à chaque appel de find par la bibliothèque d'interaction.

Tester votre programme

Placez milk.cpp, milk.h et le fichier grader.cpp fourni en pièce jointe dans le même répertoire, puis compilez avec C++17 :

g++ grader.cpp milk.cpp -o milk -O2 -std=c++17
./milk < ex_milk1.in

Pour le fichier exécutable milk ainsi obtenu :

La première ligne de l'entrée de la bibliothèque d'interaction contient deux entiers non négatifs $id,t$, désignant respectivement le numéro du test et le nombre de cas de test.

Pour chaque cas de test, la première ligne contient un entier strictement positif $n$, le nombre de villes. Chacune des lignes $2\sim n$ contient deux entiers strictement positifs $u_{i,1}$, $v_{i,1}$ ; chacune des $n-1$ lignes suivantes contient deux entiers strictement positifs $u_{i,2}$, $v_{i,2}$.

Si les réponses des $t$ appels à find sont toutes correctes, la bibliothèque d'interaction affiche Correct! sur la première ligne et Max queries used: Q sur la deuxième, où $Q$ est le nombre maximal d'appels à query parmi tous les cas de test. Si au moins une réponse est incorrecte, elle affiche Wrong answer. ; si un appel à l'interface est invalide, la raison de l'erreur est également indiquée sur la sortie d'erreur standard.

Exemples

Entrée 1

0 3
5
1 5
2 5
2 4
3 5
1 2
1 4
3 4
4 5
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
1 7
2 4
3 6
4 6
5 7
5 8
6 8
2
1 2
1 2

Sortie 1

Correct!
Max queries used: 28

Remarque

Attention : les données des tests finaux ne contiennent pas les exemples.

Sur les figures, une arête rouge indique qu'un morceau de gâteau se trouve sur la route entre les deux villes, et une arête bleue indique qu'une portion de pudding s'y trouve.

Pour le premier cas de test, les arbres formés par les routes contenant des gâteaux et des puddings ont la forme suivante :

Pour le deuxième cas de test, les arbres formés par les routes contenant des gâteaux et des puddings ont la forme suivante :

Pour le troisième cas de test, une même route peut contenir à la fois du gâteau et du pudding.

Contraintes

Propriété particulière $\text{A}$ : les positions des gâteaux et des puddings sont générées de manière purement aléatoire.

Propriété particulière $\text{B}$ : il est garanti qu'il existe une seule réponse possible.

Propriété particulière $\text{C}$ : si l'on enracine en la ville $1$ les deux arbres formés par les routes contenant des gâteaux et des puddings, puis que l'on ajoute, pour chaque ville, une arête dirigée vers sa ville parente dans chacun des deux arbres, le graphe orienté obtenu est un DAG.

Propriété particulière $\text{D}$ : si l'on enracine en la ville $2$ les deux arbres formés par les routes contenant des gâteaux et des puddings, puis que l'on ajoute, pour chaque ville, une arête dirigée vers sa ville parente dans chacun des deux arbres, le graphe orienté obtenu est un DAG.

Propriété particulière $\text{E}$ : les positions des puddings sont générées de manière purement aléatoire. Les positions des gâteaux ne dépendent pas des positions des puddings.

Propriété particulière $\text{F}$ : les deux arbres formés par les routes contenant des gâteaux et des puddings sont deux chaînes, ayant toutes deux la ville $1$ pour tête.

Dans ce problème, la génération aléatoire d'un arbre est définie par une séquence de Prufer aléatoire.

Sous-tâches

Si la réponse renvoyée par find est incorrecte ou si les paramètres de query sont invalides, le coefficient multiplicateur du score de ce test est $0$.

Pour les sous-tâches $1,2,3$, si le nombre de requêtes dépasse $\frac{n\times(n-1)}{2}$, le coefficient multiplicateur du score de ce test est $0$ ; sinon, il est $1$.

Pour les sous-tâches $4\sim 15$, soit $Q$ le nombre maximal d'appels à query parmi tous les cas de test. Le coefficient multiplicateur du score $f(Q)$ est calculé selon le tableau suivant :

Le score final du test est égal à son nombre de points multiplié par le coefficient multiplicateur du score, avec trois chiffres après la virgule conformément aux règles d'UOJ pour les scores réels.

Limite de temps : $20\ \mathrm{s}$.

Limite de mémoire : $512\ \mathrm{MiB}$.