Il neige en hiver dans de nombreuses régions de Russie. La Russie compte $N$ villes, numérotées de $0$ à $N-1$, et $N-1$ routes, numérotées de $0$ à $N-2$. La route $i$ ($0 \le i \le N-2$) relie dans les deux sens deux villes distinctes $A_i,B_i$ ($0 \le A_i < B_i \le N-1$). Il est possible de se déplacer entre n'importe quelles deux villes distinctes en empruntant des routes.

L'état d'enneigement de chaque route varie d'un jour à l'autre. Chaque jour, pour chaque route, soit il neige, soit il ne neige pas. Cet état ne change pas au cours de la journée.

Anya et Boris travaillent au service des transports russe. Anya appartient au département chargé de gérer les informations routières, et Boris à celui chargé de répondre aux questions des citoyens. Chaque question demande le nombre minimal de routes sur lesquelles il neige qu'il faut emprunter pour aller de la ville $0$, capitale de la Russie, à une autre ville donnée. Habituellement, après avoir reçu une question, Boris échange avec Anya avant de répondre au citoyen.

Un championnat du monde de programmation va se tenir en Russie pendant $Q$ jours. Pendant cette période, les lignes de communication seront encombrées et il sera difficile pour Anya et Boris d'échanger directement. Ils décident donc de communiquer ainsi :

• Au début de chaque journée, Anya reçoit les informations d'enneigement du jour et envoie des données à un serveur relais.
• Lorsque Boris reçoit une question d'un citoyen, il y répond en consultant le serveur relais.

Leurs échanges sont toutefois soumis aux contraintes suivantes :

• Le serveur relais a une capacité de $L=1\,000$ bits. Anya peut y stocker au plus $L$ bits d'information.
• Au début de chaque journée, toutes les données stockées sur le serveur sont initialisées à $0$.
• Lors d'un échange avec le serveur, Boris peut lire un bit à une position de son choix.
• Pour répondre à chaque question, Boris peut consulter le serveur au plus 20 fois.

Vous connaissez le directeur du service des transports et êtes chargé de concevoir les stratégies d'Anya et de Boris.

Tâche

Écrivez des programmes qui mettent en œuvre les stratégies d'Anya et de Boris afin de répondre correctement aux questions des citoyens.

Détails d'implémentation

Vous devez soumettre deux fichiers écrits dans le même langage de programmation.

Le premier fichier doit s'appeler Anya.c ou Anya.cpp. Il met en œuvre la stratégie d'Anya et doit implémenter les deux routines suivantes. Le programme doit inclure Anyalib.h.

void InitAnya(int N, int A[], int B[])

Cette fonction est appelée une seule fois par test.

• Le paramètre $N$ représente le nombre de villes.
• Les paramètres A[] et B[] sont chacun une suite de longueur $N-1$ décrivant les connexions routières. Les éléments $A[i]$ et $B[i]$ ($0 \le i \le N-2$) sont des entiers indiquant que la route $i$ relie dans les deux sens les villes $A[i]$ et $B[i]$, et vérifient $0 \le A[i] < B[i] \le N-1$.

void Anya(int C[])

Cette fonction est appelée $Q$ fois après l'appel à InitAnya. Elle correspond au choix, par Anya, de la suite de bits à stocker sur le serveur relais après la mise à jour des informations d'enneigement au début d'une journée.

• Le paramètre C[] est une suite de longueur $N-1$ décrivant l'enneigement des routes. L'élément $C[i]$ ($0 \le i \le N-2$) est un entier égal à $0$ ou $1$ : $C[i]=1$ signifie qu'il neige sur la route $i$, et $C[i]=0$ qu'il n'y neige pas.

La fonction Anya peut appeler la fonction suivante :

void Save(int place, int bit)

Cette fonction représente l'enregistrement d'un bit sur le serveur relais par Anya.

• Le paramètre $place$ désigne la position où écrire le bit. Il doit être un entier compris entre $0$ et $L-1$ inclus. Une valeur hors de cet intervalle entraîne le verdict « Réponse incorrecte [1] ». De plus, pendant chaque appel à Anya, il est interdit d'appeler cette fonction plusieurs fois avec le même paramètre $place$. Deux appels avec la même valeur entraînent le verdict « Réponse incorrecte [2] ».
• Le paramètre $bit$ est l'entier à écrire et doit valoir $0$ ou $1$. Toute autre valeur entraîne le verdict « Réponse incorrecte [3] ».

Après l'appel à Save, le bit à la position $place$ du serveur vaut $bit$.

Si un appel à Save entraîne un verdict de réponse incorrecte, le programme se termine immédiatement.

Juste avant chaque appel à Anya, tous les bits du serveur sont toujours initialisés à $0$. Ainsi, à la fin de Anya, les positions où aucune écriture par Save n'a été effectuée contiennent $0$.

Le deuxième fichier doit s'appeler Boris.c ou Boris.cpp. Il met en œuvre la stratégie de Boris et doit implémenter les deux routines suivantes. Le programme doit inclure Borislib.h.

void InitBoris(int N, int A[], int B[])

Cette fonction est appelée une seule fois par test.

• Le paramètre $N$ représente le nombre de villes.
• Les paramètres A[] et B[] sont chacun une suite de longueur $N-1$ décrivant les connexions routières. Les éléments $A[i]$ et $B[i]$ ($0 \le i \le N-2$) sont des entiers indiquant que la route $i$ relie dans les deux sens les villes $A[i]$ et $B[i]$, et vérifient $0 \le A[i] < B[i] \le N-1$.

int Boris(int city)

Cette fonction est appelée plusieurs fois après l'appel à InitBoris. Elle correspond aux actions de Boris pour répondre à une question d'un citoyen.

• Le paramètre $city$ représente la question du citoyen. Il s'agit d'un entier compris entre $1$ et $N-1$ inclus. Le citoyen demande le nombre minimal de routes sur lesquelles il neige qu'il faut emprunter pour aller de la ville $0$ à la ville $city$.
• La fonction Boris doit renvoyer un entier compris entre $0$ et $N-1$ inclus, qui constitue la réponse à la question. Une valeur hors de cet intervalle entraîne le verdict « Réponse incorrecte [4] ». Une réponse fausse entraîne le verdict « Réponse incorrecte [7] ».

La fonction Boris peut appeler la fonction suivante :

int Ask(int place)

Cette fonction représente la lecture d'un bit du serveur relais par Boris.

• Le paramètre $place$ désigne la position du bit à lire. Il doit être un entier compris entre $0$ et $L-1$ inclus. Une valeur hors de cet intervalle entraîne le verdict « Réponse incorrecte [5] ».

La valeur renvoyée par Ask est un entier égal à $0$ ou $1$, représentant le contenu du bit à la position $place$ du serveur. Pendant chaque appel à Boris, la fonction Ask peut être appelée au plus 20 fois. Plus de 20 appels entraînent le verdict « Réponse incorrecte [6] ».

Si un appel à Ask entraîne un verdict de réponse incorrecte, le programme se termine immédiatement.

Procédure d'évaluation

L'évaluation suit la procédure ci-dessous. Le programme se termine immédiatement dès qu'un verdict de réponse incorrecte est prononcé.

1. Pour fournir les informations routières, InitAnya puis InitBoris sont appelées une fois chacune, dans cet ordre.

2. Pour $i=1,\ldots,Q$, les opérations suivantes sont effectuées dans l'ordre :

   • La fonction Anya est appelée une fois. Cela correspond au choix, par Anya, de la suite de bits à stocker sur le serveur après la mise à jour des informations d'enneigement au début de la journée.
   • La fonction Boris est appelée $D_i$ fois, où $D_i$ est le nombre de questions posées par les citoyens le $i$-ème jour. Le paramètre du $j$-ème appel ($1 \le j \le D_i$) est $R_{ij}$ ($1 \le R_{ij} \le N-1$). Si la valeur renvoyée par ce $j$-ème appel ne correspond pas au nombre minimal de routes sur lesquelles il neige qu'il faut emprunter pour aller de la ville $0$ à la ville $R_{ij}$, la réponse est incorrecte.

3. Si aucun verdict de réponse incorrecte n'a été prononcé, la réponse est acceptée.

Remarques importantes

• Les étapes (1) et (2) de la « Procédure d'évaluation » sont prises en compte pour mesurer le temps d'exécution et la mémoire utilisée. Si la solution est correcte, à l'étape (2), Anya est appelée $Q$ fois au total et Boris est appelée $D_1+\cdots+D_Q$ fois au total.
• Anya et Boris ne peuvent pas connaître les valeurs $D_1,\ldots,D_Q$.
• La fonction Boris ne reçoit aucune information indiquant à quel moment Anya a mis à jour les données stockées sur le serveur.
• Vous pouvez implémenter d'autres routines pour un usage interne et déclarer des variables globales. Toutefois, les deux programmes soumis sont liés avec l'évaluateur pour former un seul exécutable. Toutes les variables globales et routines internes de chaque fichier, à l'exception de InitAnya, Anya, InitBoris et Boris, doivent donc être déclarées static afin d'éviter les conflits avec les autres fichiers. Lors de l'évaluation, le programme est exécuté dans deux processus, l'un pour Anya et l'autre pour Boris : les deux côtés ne peuvent donc pas partager leurs variables globales.
• Votre soumission ne doit communiquer d'aucune manière avec l'entrée standard, la sortie standard ou d'autres fichiers.

Compilation et exécution

Un exemple d'évaluateur pour tester vos programmes est inclus dans une archive téléchargeable sur le site du concours. Cette archive contient également des exemples des fichiers à soumettre.

L'exemple d'évaluateur se compose d'un fichier, grader.c ou grader.cpp. Si vos programmes s'appellent Anya.c et Boris.c, ou Anya.cpp et Boris.cpp, exécutez les commandes suivantes pour les tester.

• Pour C :

gcc -std=c11 -O2 -o grader grader.c Anya.c Boris.c -lm

• Pour C++ :

g++ -std=c++11 -O2 -o grader grader.cpp Anya.cpp Boris.cpp

Si la compilation réussit, un exécutable nommé grader est créé.

Attention : l'évaluateur réel diffère de cet exemple. L'exemple est lancé dans un seul processus. Il lit les données sur l'entrée standard et écrit les résultats sur la sortie standard.

Présentation de l'exemple d'évaluateur

L'exemple d'évaluateur appelle les fonctions conformément à la « Procédure d'évaluation ».

Le point suivant diffère du comportement de l'évaluateur réel :

• L'exemple d'évaluateur ne vérifie pas le verdict « Réponse incorrecte [7] » ; à la place, il affiche la valeur renvoyée par Boris pour chaque question.

Entrée de l'exemple d'évaluateur

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

• La première ligne contient un entier $N$, le nombre de villes.
• La $(i+1)$-ème ligne ($0 \le i \le N-2$) parmi les $N-1$ lignes suivantes contient deux entiers $A_i,B_i$ séparés par un espace, indiquant que la route $i$ relie les villes $A_i$ et $B_i$ dans les deux sens.
• La ligne suivante contient un entier $Q$, indiquant que le championnat dure $Q$ jours.
• La $i$-ème ligne ($1 \le i \le Q$) parmi les $Q$ lignes suivantes contient une chaîne $S_i$ de longueur $N-1$ et $D_i+1$ entiers, séparés par des espaces. $S_i$ représente l'enneigement le $i$-ème jour : son $(j+1)$-ème caractère depuis la gauche ($0 \le j \le N-2$) vaut 1 s'il neige sur la route $j$, et 0 sinon. Le premier des $D_i+1$ entiers suivants est $D_i$. Les $D_i$ suivants sont $R_{i1},\ldots,R_{iD_i}$. Cela signifie que, le $i$-ème jour, la $j$-ème question ($1 \le j \le D_i$) porte sur le nombre minimal de routes sur lesquelles il neige qu'il faut emprunter pour aller de la ville $0$ à la ville $R_{ij}$.

Sortie de l'exemple d'évaluateur

L'exemple d'évaluateur écrit les informations suivantes sur la sortie standard (les guillemets ne sont pas réellement affichés).

• Si un verdict de réponse incorrecte est prononcé pendant l'exécution, son type est affiché sous la forme Wrong Answer [1], puis le programme se termine.
• Si aucun des $D_i$ appels à Boris effectués après le $i$-ème appel à Anya ($1 \le i \le Q$) n'entraîne de verdict de réponse incorrecte, une ligne contenant $D_i$ entiers séparés par des espaces est alors affichée. Le $j$-ème entier ($1 \le j \le D_i$) est la valeur renvoyée par $\operatorname{Boris}(R_{ij})$.

Si le programme satisfait plusieurs conditions de réponse incorrecte, un seul de ces types est affiché.

Contraintes

Toutes les données d'entrée vérifient les conditions suivantes.

• $2 \le N \le 500$.
• $1 \le Q \le 500$.
• $0 \le A_i < B_i \le N-1$ ($0 \le i \le N-2$).
• $1 \le D_j$ ($1 \le j \le Q$).
• $D_1+\cdots+D_Q \le 500$.
• Il est possible de se déplacer entre n'importe quelles deux villes distinctes en empruntant des routes.

Sous-tâches

Sous-tâche 1 [15 points]

• $N \le 20$.

Sous-tâche 2 [5 points]

• $N \le 100$.

Sous-tâche 3 [35 points]

Les conditions suivantes sont vérifiées.

• $A_i=i$ ($0 \le i \le N-2$).
• $B_i=i+1$ ($0 \le i \le N-2$).

Sous-tâche 4 [45 points]

Aucune contrainte supplémentaire.

Exemple d'interaction

Voici un exemple d'entrée lue par l'exemple d'évaluateur, accompagné des appels de fonctions correspondants.

Entrée 1

5
0 1
1 2
1 4
2 3
2
0101 3 2 4 3
1110 1 4

Exemples d'appels de routines

Attention : les appels de fonctions de cet exemple ne sont pas nécessairement significatifs.

Les paramètres transmis à InitAnya(...), à InitBoris(...), ainsi qu'aux premier et deuxième appels à Anya(...) sont respectivement les suivants.