Tämä on monivaiheinen (multi-pass) vuorovaikutteinen tehtävä. Muista tyhjentää tulostepuskuri (flush) jokaisen tulostuksen jälkeen. Voit tyhjentää tulostepuskurin seuraavasti:

• fflush(stdout) tai cout.flush() C/C++:ssa;
• System.out.flush() Javassa ja Kotlinissa;
• sys.stdout.flush() Pythonissa.

Pelin idea ChatGPT:n kuvittamana.

Klassisessa online-parituspelissä (online matching) verkon kaaret paljastetaan yksi kerrallaan. Joka kerta, kun kaari näytetään, sinun on välittömästi ja peruuttamattomasti päätettävä, otatko sen mukaan paritukseesi. Tavoitteenasi on varmistaa, etteivät mitkään kaksi valittua kaarta jaa yhteistä solmua, samalla kun maksimoit valittujen kaarien kokonaismäärän.

Olet kunnianhimoinen tietojenkäsittelytieteilijä ja janoat mainetta. Kuten hyvin tiedät, maksimiparituksen löytäminen online-asetelmassa on todistettavasti mahdotonta suurella todennäköisyydellä – jopa kaikkein yksinkertaisimmille verkkoluokille, kuten kaksijakoisille verkoille. Mutta siinä missä muut näkevät perustavanlaatuisen esteen, sinä näet tilaisuuden kunniaan. Tänään väität ratkaisseesi puiden kauan avoimena olleen ongelman ja olet valmis paljastamaan uraauurtavan algoritmisi maailmalle.

On vain yksi ongelma: eilen löysit todistuksestasi virheen etkä vieläkään tiedä, miten korjata sen. Koska et halua luopua parrasvaloista, päätät muuttaa esityksesi taikashow'ksi – kulissien takana piilotteleva avustajasi lähettää pienen vihjeen koko $n$-solmuisesta puusta ennen pelin alkua.

Alkuperäinen suunnitelmasi oli yksinkertainen: avustajasi lähettäisi vastauksen jokaiseen kaarikyselyyn suoraan. Tätä varten olet asentanut salaisen korvanapin, joka pystyy vastaanottamaan yhden pituuden $(n - 1)$ binäärimerkkijonon. Yleisö suhtautuu kuitenkin epäilevästi ”läpimurtoosi”. Estääkseen ennalta sovitut huijaukset he vaativat, että kaaret esitetään tasajakautuneesti satunnaisessa järjestyksessä – sellaisessa, jota sinä tai avustajasi ette voi ennustaa ettekä hallita.

Näyttämö on valmis. Valonheittimet osoittavat sinuun. Todista nyt väitteesi – kanavaa vaihtamatta.

Vuorovaikutusprotokolla

Ratkaisuasi ajetaan jokaisessa testissä kahdesti. prepare-kierroksella ratkaisusi toimii avustajana. play-kierroksella ratkaisusi toimii sinuna, taikurina. Molemmilla kierroksilla ratkaisuasi arvioidaan vuorovaikutteisena proseduurina.

Valmistelukierros (Prepare Round)

Syötteen ensimmäinen rivi sisältää sanan prepare. Toinen rivi sisältää kokonaisluvun $n$ ($2 \le n \le 500$) – solmujen lukumäärän. Seuraavat $(n - 1)$ riviä sisältävät kukin kaksi kokonaislukua $u$ ja $v$ ($1 \le u, v \le n$, $u < v$), jotka ilmaisevat suuntaamattoman kaaren solmujen $u$ ja $v$ välillä puussa.

Sinun on tulostettava yksi rivi, joka sisältää täsmälleen pituuden $(n - 1)$ binäärimerkkijonon $s$, joka koostuu vain merkeistä 0 ja 1. Tämä merkkijono välitetään toiselle kierrokselle (play). Jos tulosteesi ei ole vaaditussa muodossa, saat tuomion Wrong Answer.

Pelikierros (Play Round)

Ratkaisusi käynnistetään uudelleen play-kierrosta varten.

Ensimmäinen rivi sisältää sanan play. Toinen rivi sisältää kokonaisluvun $n$. Kolmas rivi sisältää binäärimerkkijonon $s$ täsmälleen sellaisena kuin tulostit sen prepare-kierroksella.

Tämän jälkeen peli alkaa ja kestää $(n - 1)$ vuoroa. Jokaisella vuorolla annetaan rivi, joka sisältää kaksi kokonaislukua $u$ ja $v$ ($1 \le u, v \le n$, $u < v$). Vastauksena sinun tulee tulostaa yksi rivi, joka sisältää joko take tai ignore. Kaikki ensimmäisen kierroksen kaaret annetaan täsmälleen kerran, ja kaarien järjestys valitaan tasajakautuneesti satunnaisesti $(n - 1)!$ mahdollisesta permutaatiosta.

Jos tuloste on virheellisessä muodossa, peli päättyy välittömästi ilman lisätietoja interaktorilta.

Oikeellisuuden arviointi

Olkoon $M$ ratkaisusi valitsemien kaarien joukko. Suoritus hyväksytään, jos mikään solmu ei ole päätepisteenä useammalle kuin yhdelle valitulle kaarelle ja $|M| = |M^*|$, missä $M^*$ on verkon maksimiparitus.

Testejä on täsmälleen $50$, lukuun ottamatta esimerkkitestejä. Tehtävän läpäisemiseksi ratkaisusi on toimittava oikein kaikissa testeissä, mukaan lukien esimerkkitestit.

Kaikkien sekoitusten taataan olevan kiinnitettyjä ennen ratkaisun tulosteen vastaanottamista. Satunnaisuus on kiinnitetty jokaiselle testille kiinnittämällä näennäissatunnaislukugeneraattorin siemenluku (seed).

Tarjolla on testaustyökalu, jonka avulla voit kehittää ja testata ratkaisuasi.

Esimerkki

Esimerkki 1, Vaihe 1

Syöte

prepare
3
1 2
1 3

Tuloste

00

Esimerkki 1, Vaihe 2

Syöte

play
3
00
1 3

1 2

Tuloste

take

ignore

Esimerkin 1 selitys

Koska $|M^*| = 1$, minkä tahansa kaaren valitseminen kelpaa, ja vihje voi olla mielivaltainen.