Les pays A et B entretiennent de mauvaises relations. A veut découvrir le réseau ferroviaire de B pour l’envahir. Il a envoyé des espions à plusieurs reprises, mais ils ont toujours été capturés avant d’obtenir des informations utiles. A ne sait donc que ce qui suit.

• Le réseau de B comporte $N$ gares numérotées de $1$ à $N$.

• Deux gares distinctes quelconques sont reliées directement par une voie ou par l’intermédiaire d’autres gares reliées par des voies.

• Entre deux gares quelconques, il existe exactement un chemin.

• Aucune voie ne relie directement une gare à elle-même.

Constatant les limites de l’espionnage, A prévoit de corrompre un haut dirigeant de la compagnie ferroviaire de B pour obtenir un dessin du réseau. L’envoyer directement révélerait le traître ; celui-ci le modifiera donc comme suit avant de l’envoyer à A.

• Dessiner $K$ fausses voies. Choisir des gares distinctes $a$ et $b$ qui ne sont pas directement reliées dans le dessin, puis les relier par une fausse voie. Répéter cela $K$ fois.

• Placer une marque spéciale sur une gare.

• Enfin, effacer tous les numéros des gares.

Le traître transmet le dessin obtenu à A. Ces seules informations rendant difficile l’identification du réseau de B, personne ne saura que des informations secrètes ont été divulguées.

Pour réussir ce plan, il faut résoudre les problèmes suivants.

• Le dessin reçu n’a plus de numéros de gares et ne distingue pas les vraies voies des fausses. A connaît seulement la gare marquée et le fait qu’exactement $K$ fausses voies ont été ajoutées.

• L’expéditeur doit donc choisir judicieusement les fausses voies et la gare marquée afin que le destinataire distingue les vraies voies des fausses à partir du seul dessin.

• Le destinataire doit comprendre la méthode de modification et retrouver le dessin du réseau initial.

Deux fonctions sont donc nécessaires : l’une modifie le dessin et l’autre retrouve le véritable réseau. A veut vous confier ce travail.

Détails d'implémentation

Vous devez implémenter les deux fonctions suivantes.

vector< pair<int, int> > encode_map(int N, int K, int &X,
                                            vector< pair<int, int> > E)

• L’argument entier N est le nombre $N$ de gares de B. Chaque gare est représentée par un entier de $1$ à $N$, bornes incluses.

• L’argument entier K est le nombre $K$ de fausses voies à ajouter.

• L’argument X enregistre le numéro de la gare à marquer. À la fin de la fonction, il doit contenir un entier positif de $1$ à $N$, bornes incluses.

• Le tableau E a une taille de $N-1$ et représente le réseau de B. Un couple $(a,b)$ dans E signifie qu’une voie relie directement les gares $a$ et $b$.

• Renvoyez un tableau de $K$ couples $(a,b)$ indiquant des fausses voies entre des gares distinctes $a$ et $b$. Vous ne pouvez pas ajouter de fausse voie entre $a$ et $b$ si elles sont déjà reliées par une vraie ou une fausse voie.

vector< pair<int, int> > decode_map(int N, int K, int X,
                                            vector< pair<int, int> > E)

• L’argument entier N est le nombre $N$ de gares de B. Les gares sont représentées par des entiers de $1$ à $N$, bornes incluses. Comme leurs numéros ont été effacés, ceux utilisés ici peuvent différer des vrais. Ils résultent de l’application d’une bijection aux numéros utilisés par encode_map.

• L’argument entier K est le nombre $K$ de fausses voies ajoutées.

• L’argument entier X est le numéro de la gare spécialement marquée.

• Le tableau E a une taille de $N+K-1$ et représente le dessin transmis à A. Un couple $(a,b)$ signifie que les gares $a$ et $b$ sont directement reliées par une vraie ou une fausse voie dans le dessin. L’ordre des éléments de E n’a aucune signification.

• Cette fonction reconstitue le dessin initial à partir de celui produit par encode_map. Renvoyez un tableau de $N-1$ couples $(a,b)$ contenant le réseau de B.

Aucune fonction d’entrée ou de sortie ne doit être appelée dans le code source soumis.

Chaque test contient un ou plusieurs scénarios indépendants. Pour un test de $T$ scénarios, le programme appelant ces fonctions est exécuté exactement deux fois, comme suit.

Lors de la première exécution :

• encode_map est appelée $T$ fois.

• Les résultats de encode_map sont enregistrés par le système d’évaluation.

• decode_map n’est pas appelée.

Lors de la seconde exécution :

• decode_map est appelée plusieurs fois. À chaque appel, un scénario arbitraire est choisi et le dessin produit pour celui-ci par encode_map sert d’entrée à decode_map.

• encode_map n’est pas appelée.

Le temps d’exécution et la mémoire utilisée sont calculés en combinant les deux exécutions.

Contraintes

• $1 \le T \le 200$

• $3 \le N \le 200$

• $1 \le K < \frac{N}{2}$

Sous-tâches

1. ($4$ points) $N \le 4$.

2. ($13$ points) $K=1$.

3. ($11$ points) Chaque gare est reliée à au plus deux voies.

4. ($29$ points) Toute gare peut atteindre toute autre gare en empruntant au plus $\lfloor N/2 \rfloor$ voies.

5. ($43$ points) Aucune contrainte supplémentaire.

Sous-tâches

Un test est correct uniquement si encode_map produit un dessin valide et si decode_map retrouve correctement le réseau. Si le tableau renvoyé par decode_map contient ne serait-ce qu’une fausse voie, le score de ce test est $0$. L’ordre des éléments dans les tableaux renvoyés par les deux fonctions n’importe pas.

Le score d’une sous-tâche est le minimum des scores de tous ses tests.

Exemples

• Considérons $N=6$, $K=1$ et les voies $E=[(1,2),(1,3),(1,4),(4,5),(4,6)]$.

Le programme d’évaluation appelle la fonction suivante.

encode_map(6, 1, X, [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)])

Le dessin de gauche représente le réseau de B. Ajouter la fausse voie $(4,2)$ et marquer la gare $1$ donne le dessin de droite. Ici, encode_map renvoie [(4, 2)] et place $1$ dans X. D’autres réponses peuvent exister.

Ensuite, le programme d’évaluation appelle la fonction suivante. L’ordre des éléments du tableau du dernier argument peut varier.

decode_map(6, 1, 2, [(1, 5), (2, 3), (2, 4), (2, 5), (3, 5), (5, 6)])

Le dessin représenté par l’entrée est montré ci-dessous. Les numéros des gares diffèrent de ceux utilisés par encode_map.

La fonction renvoie [(3, 2), (4, 2), (5, 6), (1, 5), (5, 2)]. L’ordre peut varier.

Cet exemple satisfait les conditions des sous-tâches $2$, $4$ et $5$.

Programme d’évaluation d’exemple

Le programme d’évaluation d’exemple lit l’entrée au format suivant.

• Ligne $1$ : $T$

Suivent $T$ blocs représentant chacun un scénario. Chaque bloc a le format suivant.

• Ligne $1$ : $N\ K$

• Ligne $1+i$ ($1 \le i \le N-1$) : $a_i\ b_i$

Le couple $a_i,b_i$ indique une voie entre les gares $a_i$ et $b_i$.

Pour chaque scénario, le programme d’évaluation d’exemple affiche ce qui suit.

• Ligne $1$ : le tableau renvoyé par encode_map.

• Ligne $2$ : le tableau renvoyé par decode_map.

Le programme d’évaluation d’exemple peut différer de celui utilisé pour l’évaluation réelle.