Dette er et interaktivt flertrinnsproblem (multi-pass). Husk å tømme utdatabufferen (flush) etter hver utskrift. For å tømme utdataen din kan du bruke:

• fflush(stdout) eller cout.flush() i C/C++;
• System.out.flush() i Java og Kotlin;
• sys.stdout.flush() i Python.

Konseptet i spillet, illustrert av ChatGPT.

I det klassiske online-matchingsspillet avsløres kantene i en graf én etter én. Hver gang en kant vises, må du umiddelbart og ugjenkallelig bestemme om du vil inkludere den i matchingen din. Målet ditt er å sikre at ingen to valgte kanter deler en node, samtidig som du maksimerer det totale antallet valgte kanter.

Du er en ambisiøs informatiker, sulten på berømmelse. Som du godt vet, er det beviselig umulig med høy sannsynlighet å finne en maksimal matching i en online-setting — selv for de enkleste grafklassene som.bipartitte grafer. Men der andre ser en fundamental barriere, ser du en mulighet for heder og ære. I dag hevder du å ha knekt det lenge åpne problemet for trær, og du er klar til å avsløre den banebrytende algoritmen din for verden.

Det er bare ett problem: i går oppdaget du en feil i beviset ditt, og du aner fortsatt ikke hvordan du skal fikse den. Uvillig til å forlate rampelyset bestemmer du deg for å gjøre demonstrasjonen om til et trylleshow — assistenten din, gjemt bak scenen, vil sende et lite hint om hele treet med $n$ noder før spillet starter.

Den opprinnelige planen din var enkel: la assistenten sende svaret på hver kantspørring direkte. Til dette formålet har du installert en hemmelig ørepropp som kan motta én enkelt binærstreng med lengde $(n - 1)$. Men publikum er skeptiske til «gjennombruddet» ditt. For å forhindre ethvert avtalt juks krever de at kantene presenteres i en uniformt tilfeldig rekkefølge — en som verken du eller assistenten din kan forutsi eller kontrollere.

Scenen er satt. Lysene er rettet mot deg. Bevis nå påstanden din — uten å bytte kanal.

Interaksjonsprotokoll

Løsningen din kjøres to ganger på hver test. I runden prepare opptrer løsningen din som assistenten. I runden play opptrer løsningen din som deg, tryllekunstneren. I begge rundene blir løsningen din evaluert som en interaktiv prosedyre.

Forberedelsesrunde (Prepare Round)

Den første linjen i inndataene inneholder ordet prepare. Den andre linjen inneholder et heltall $n$ ($2 \le n \le 500$) — antallet noder. De følgende $(n - 1)$ linjene inneholder hver to heltall $u$ og $v$ ($1 \le u, v \le n$, $u < v$), som angir en urettet kant mellom $u$ og $v$ i treet.

Du må skrive ut én linje som inneholder en binærstreng $s$ med lengde nøyaktig $(n - 1)$ bestående kun av tegnene 0 og 1. Dette er strengen som sendes til den andre runden (play). Hvis utdataen din ikke samsvarer med ønsket format, vil du få dommen Wrong Answer.

Spillerunde (Play Round)

Løsningen din blir startet på nytt for runden play.

Den første linjen inneholder ordet play. Den andre linjen inneholder heltallet $n$. Den tredje linjen inneholder binærstrengen $s$ nøyaktig slik du skrev den ut i runden prepare.

Deretter starter spillet med $(n - 1)$ trekk. I hvert trekk blir det gitt en linje som inneholder to heltall $u$ og $v$ ($1 \le u, v \le n$, $u < v$). Som svar skal du skrive ut én linje som inneholder enten take eller ignore. Alle kantene fra den første runden vil bli gitt nøyaktig én gang, og rekkefølgen på kantene velges uniformt tilfeldig blant de $(n - 1)!$ mulige permutasjonene.

Hvis det kommer utdata i ugyldig format, avsluttes spillet umiddelbart uten videre informasjon fra interaktoren.

Evaluering av korrekthet

La $M$ være mengden av kanter løsningen din tar. Det regnes som akseptabelt dersom ingen node er insident med mer enn én valgt kant og $|M| = |M^*|$, der $M^*$ er den maksimale matchingen i grafen.

Det er nøyaktig $50$ tester, utenom eksempeltestene. For å bestå oppgaven må løsningen din være riktig på alle testene, inkludert eksempeltestene.

Alle stokkinger garanteres å være fastsatt før løsningens utdata mottas. Tilfeldigheten er låst for hver test ved å låse frøet (seed) til en pseudotilfeldig tallgenerator.

Et testverktøy er tilgjengelig for å hjelpe deg med å utvikle og teste løsningen din.

Eksempel

Eksempel 1, Omgang 1

Inndata

prepare
3
1 2
1 3

Utdata

00

Eksempel 1, Omgang 2

Inndata

play
3
00
1 3

1 2

Utdata

take

ignore

Forklaring av Eksempel 1

Siden $|M^*| = 1$, er det akseptabelt å ta hvilken som helst kant, og hintet kan være vilkårlig.