Ceci est un problème interactif à plusieurs passages. N'oubliez pas de vider le tampon de sortie après chaque impression. Pour vider votre sortie, vous pouvez utiliser :
fflush(stdout)oucout.flush()en C/C++ ;System.out.flush()en Java et Kotlin ;sys.stdout.flush()en Python.
Dans le jeu de couplage en ligne classique, les arêtes d'un graphe sont révélées une par une. Chaque fois qu'une arête est montrée, vous devez décider immédiatement et irrévocablement si vous l'incluez dans votre couplage. Votre objectif est de vous assurer qu'aucune des deux arêtes choisies ne partage un sommet tout en maximisant le nombre total d'arêtes sélectionnées.
Vous êtes un informaticien ambitieux, avide de célébrité. Comme vous le savez bien, trouver un couplage maximum dans un cadre en ligne est prouvé impossible avec une probabilité élevée — même pour les classes de graphes les plus simples comme les graphes bipartis. Pourtant, là où d'autres voient une barrière fondamentale, vous voyez une opportunité de gloire. Aujourd'hui, vous prétendez avoir résolu le problème ouvert de longue date pour les arbres et êtes prêt à dévoiler votre algorithme révolutionnaire au monde entier.
Il n'y a qu'un seul problème : hier, vous avez découvert un bug dans votre preuve, et vous n'avez toujours aucune idée de comment le corriger. Ne voulant pas abandonner les projecteurs, vous décidez de transformer votre démonstration en un spectacle de magie — votre assistant, caché en coulisses, transmettra un petit indice sur l'arbre entier avec $n$ sommets avant que le jeu ne commence.
Votre plan initial était simple : demander à votre assistant d'envoyer la réponse à chaque requête d'arête directement. À cette fin, vous avez installé une oreillette secrète capable de recevoir une chaîne binaire unique de longueur $(n - 1)$. Mais le public est sceptique quant à votre « percée ». Pour éviter toute tricherie pré-arrangée, ils exigent que les arêtes soient présentées dans un ordre uniformément aléatoire — un ordre que ni vous ni votre assistant ne pouvez prédire ou contrôler.
La scène est prête. Les projecteurs sont braqués sur vous. Prouvez maintenant votre affirmation — sans changer de chaîne.
Interaction
Votre solution est exécutée deux fois sur chaque test. Dans le tour prepare, votre solution agira en tant qu'assistant. Dans le tour play, votre solution agira en tant que vous, le magicien. Dans l'un ou l'autre des tours, votre solution sera évaluée en tant que procédure interactive.
Tour prepare
La première ligne de l'entrée contient le mot prepare. La deuxième ligne contient un entier $n$ ($2 \le n \le 500$) — le nombre de sommets. Les $(n - 1)$ lignes suivantes contiennent chacune deux entiers $u$ et $v$ ($1 \le u, v \le n, u < v$), désignant une arête non orientée entre $u$ et $v$ dans l'arbre.
Vous devez afficher une ligne contenant une chaîne binaire $s$ de longueur exactement $(n - 1)$ composée uniquement des caractères 0 et 1. Il s'agit de la chaîne transmise au second tour play. Si votre sortie ne correspond pas au format souhaité, vous recevrez le verdict Wrong Answer.
Tour play
Votre solution sera redémarrée pour le tour play.
La première ligne contient le mot play. La deuxième ligne contient l'entier $n$. La troisième ligne contient la chaîne binaire $s$ exactement telle que vous l'avez imprimée lors du tour prepare.
Après cela, le jeu commence avec $(n - 1)$ tours. À chaque tour, une ligne contenant deux entiers $u$ et $v$ ($1 \le u, v \le n, u < v$) sera fournie. En réponse, vous devez afficher une ligne contenant soit take, soit ignore. Toutes les arêtes du premier tour seront fournies exactement une fois, et l'ordre des arêtes est choisi uniformément au hasard parmi les $(n - 1)!$ permutations possibles.
Lorsqu'il y a une sortie dans un format invalide, le jeu se terminera immédiatement sans autre information de l'interacteur.
Évaluation de la correction
Soit $M$ l'ensemble des arêtes que votre solution prend. Il est considéré comme acceptable si aucun sommet n'est incident à plus d'une arête prise et $|M| = |M^*|$, où $M^*$ est le couplage maximum du graphe.
Il y a exactement 50 tests, sans compter les tests d'exemple. Afin de réussir le problème, votre solution doit être correcte sur tous les tests, y compris les tests d'exemple.
Tous les mélanges sont garantis d'être fixés avant de recevoir la sortie de la solution. Le caractère aléatoire est fixé pour chaque test, implémenté en fixant la graine d'un générateur de nombres pseudo-aléatoires.
Un outil de test est fourni pour vous aider à développer et tester votre solution.
Exemples
Entrée 1
prepare 3 1 2 1 3
Sortie 1
00
Entrée 2
play 3 00 1 3 1 2
Sortie 2
take ignore
Remarque
Explication de l'exemple 1 : Puisque $|M^*| = 1$, prendre n'importe quelle arête est acceptable, et l'indice peut être arbitraire.
Figure 1. Magically Marked Matching Master