Dies ist ein interaktives Multi-Pass-Problem. Denken Sie daran, nach jeder Ausgabe den Ausgabepuffer zu leeren (flushen). Zum Leeren des Ausgabepuffers können Sie Folgendes verwenden:

• fflush(stdout) oder cout.flush() in C/C++;
• System.out.flush() in Java und Kotlin;
• sys.stdout.flush() in Python.

Das Konzept des Spiels, illustriert von ChatGPT.

Im klassischen Online-Matching-Spiel werden die Kanten eines Graphen nacheinander einzeln aufgedeckt. Jedes Mal, wenn eine Kante gezeigt wird, müssen Sie sofort und unwiderruflich entscheiden, ob Sie diese in Ihr Matching aufnehmen. Ihr Ziel ist es, sicherzustellen, dass keine zwei gewählten Kanten einen gemeinsamen Knoten teilen, während Sie gleichzeitig die Gesamtzahl der ausgewählten Kanten maximieren.

Sie sind ein ehrgeiziger Informatiker, hungrig nach Ruhm. Wie Sie nur zu gut wissen, ist das Finden eines maximalen Matchings im Online-Szenario mit hoher Wahrscheinlichkeit nachweislich unmöglich — selbst für die einfachsten Graphenklassen wie bipartite Graphen. Doch wo andere eine fundamentale Barriere sehen, wittern Sie eine Gelegenheit für unsterblichen Ruhm. Heute behaupten Sie, das seit Langem offene Problem für Bäume gelöst zu haben, und sind bereit, der Welt Ihren bahnbrechenden Algorithmus zu präsentieren.

Es gibt nur ein Problem: Gestern haben Sie einen Fehler in Ihrem Beweis entdeckt, und Sie haben noch immer keine Ahnung, wie Sie ihn beheben können. Da Sie das Rampenlicht nicht aufgeben wollen, beschließen Sie, Ihre Vorführung in eine Zaubershow zu verwandeln — Ihr hinter der Bühne versteckter Assistent wird Ihnen vor Spielbeginn einen kleinen Hinweis über den gesamten Baum mit $n$ Knoten übermitteln.

Ihr ursprünglicher Plan war simpel: Ihr Assistent sollte einfach direkt die Antwort für jede Kantenanfrage senden. Zu diesem Zweck haben Sie einen geheimen Ohrhörer installiert, der genau eine Binärzeichenkette der Länge $(n - 1)$ empfangen kann. Doch das Publikum steht Ihrem „Durchbruch“ skeptisch gegenüber. Um jede vorher abgesprochene Trickserei zu verhindern, verlangt es, dass die Kanten in einer gleichverteilt zufälligen Reihenfolge präsentiert werden — einer Reihenfolge, die weder Sie noch Ihr Assistent vorhersagen oder beeinflussen können.

Die Bühne ist bereitet. Die Scheinwerfer sind auf Sie gerichtet. Beweisen Sie nun Ihre Behauptung — ohne den Kanal zu wechseln.

Interaktionsprotokoll

Ihre Lösung wird bei jedem Test zweimal ausgeführt. In der Runde prepare agiert Ihre Lösung als Assistent. In der Runde play agiert Ihre Lösung als Sie, der Magier. In beiden Runden wird Ihre Lösung als interaktives Verfahren ausgewertet.

Vorbereitungsrunde (Prepare Round)

Die erste Zeile der Eingabe enthält das Wort prepare. Die zweite Zeile enthält eine ganze Zahl $n$ ($2 \le n \le 500$) — die Anzahl der Knoten. Die folgenden $(n - 1)$ Zeilen enthalten jeweils zwei ganze Zahlen $u$ und $v$ ($1 \le u, v \le n$, $u < v$), die eine ungerichtete Kante zwischen $u$ und $v$ im Baum bezeichnen.

Sie müssen eine Zeile ausgeben, die eine Binärzeichenkette $s$ der Länge exakt $(n - 1)$ enthält, welche ausschließlich aus den Zeichen 0 und 1 besteht. Dies ist die Zeichenkette, die an die zweite Runde (play) übertragen wird. Wenn Ihre Ausgabe nicht dem gewünschten Format entspricht, erhalten Sie das Urteil Wrong Answer.

Spielrunde (Play Round)

Ihre Lösung wird für die Runde play neu gestartet.

Die erste Zeile enthält das Wort play. Die zweite Zeile enthält die ganze Zahl $n$. Die dritte Zeile enthält die Binärzeichenkette $s$ genau so, wie Sie sie in der Runde prepare ausgegeben haben.

Danach beginnt das Spiel mit $(n - 1)$ Zügen. In jedem Zug wird eine Zeile mit zwei ganzen Zahlen $u$ und $v$ ($1 \le u, v \le n$, $u < v$) bereitgestellt. Als Antwort müssen Sie eine Zeile ausgeben, die entweder take oder ignore enthält. Alle Kanten aus der ersten Runde werden genau einmal angegeben, und die Reihenfolge der Kanten wird gleichverteilt zufällig aus allen $(n - 1)!$ möglichen Permutationen gewählt.

Sobald eine Ausgabe in ungültigem Format erfolgt, wird das Spiel sofort ohne weitere Informationen vom Interaktor beendet.

Bewertung der Korrektheit

Sei $M$ die Menge der Kanten, die Ihre Lösung auswählt. Das Ergebnis gilt als akzeptabel, wenn kein Knoten zu mehr als einer ausgewählten Kante inzident ist und $|M| = |M^*|$ gilt, wobei $M^*$ das maximale Matching des Graphen ist.

Es gibt genau $50$ Tests, ausschließlich der Beispieltests. Um das Problem zu bestehen, muss Ihre Lösung bei allen Tests einschließlich der Beispieltests korrekt sein.

Alle Zufallsreihenfolgen sind garantiert festgelegt, bevor die Ausgabe der Lösung empfangen wird. Die Zufälligkeit ist für jeden Test fest vorgegeben, implementiert durch das Fixieren des Seeds eines Pseudozufallszahlengenerators.

Ein Testwerkzeug wird bereitgestellt, um Ihnen bei der Entwicklung und dem Testen Ihrer Lösung zu helfen.

Beispiel

Beispiel 1, Durchgang 1

Eingabe

prepare
3
1 2
1 3

Ausgabe

00

Beispiel 1, Durchgang 2

Eingabe

play
3
00
1 3

1 2

Ausgabe

take

ignore

Erklärung zu Beispiel 1

Da $|M^*| = 1$ ist, ist die Auswahl einer beliebigen Kante akzeptabel, und der Hinweis kann beliebig gewählt werden.