Þetta er fjölumferða (multi-pass) gagnvirkt verkefni. Mundu að tæma úttaksbiðminnið (flush) eftir hverja prentun. Til að tæma úttakið geturðu notað:

• fflush(stdout) eða cout.flush() í C/C++;
• System.out.flush() í Java og Kotlin;
• sys.stdout.flush() í Python.

Hugmyndin að baki leiknum, myndskreytt af ChatGPT.

Í hinum klassíska netpörunarleik (online matching) eru leggir netsins afhjúpaðir einn af öðrum. Í hvert sinn sem leggur er sýndur verður þú samstundis og óafturkallanlega að ákveða hvort þú viljir taka hann með í pörunina þína. Markmið þitt er að tryggja að engir tveir valdir leggir deili sama hnúti á meðan þú hámarkar heildarfjölda valinna leggja.

Þú ert metnaðarfullur tölvunarfræðingur, þyrstur í frægð. Eins og þú veist mætavel er sannanlega ómögulegt með miklum líkum að finna hámarkspörun í netumhverfi — jafnvel fyrir einföldustu flokka neta eins og tvíhlutanet. En þar sem aðrir sjá óyfirstíganlega hindrun sérð þú tækifæri til frægðar. Í dag heldurðu því fram að þú hafir leyst hið langvinna óleysta vandamál fyrir tré og ert tilbúinn að afhjúpa byltingarkennda reikniritið þitt fyrir heiminum.

Það er bara eitt vandamál: í gær uppgötvaðir þú villu í sönnuninni þinni og þú hefur enn enga hugmynd um hvernig á að laga hana. Þar sem þú vilt ekki yfirgefa sviðsljósið ákveðurðu að breyta sýningunni þinni í töfrasýningu — aðstoðarmaður þinn, falinn baksviðs, mun senda örlitla vísbendingu um allt tréð með $n$ hnútum áður en leikurinn hefst.

Upphaflega áætlunin þín var einföld: láta aðstoðarmanninn senda svarið við hverri leggjafyrirspurn beint. Í þessu skyni hefurðu komið fyrir leynilegu heyrnartóli sem getur tekið á móti einni tvíundarunu af lengd $(n - 1)$. En áhorfendur eru efins um „byltinguna“ þína. Til að koma í veg fyrir öll fyrirfram ákveðin brögð krefjast þeir þess að leggirnir verði birtir í jafndreifðri slembiröð — röð sem hvorki þú né aðstoðarmaður þinn getið séð fyrir eða stjórnað.

Sviðið er tilbúið. Kastararnir beinast að þér. Sannaðu nú fullyrðingu þína — án þess að skipta um rás.

Samskiptareglur

Lausnin þín er keyrð tvisvar á hverju prófi. Í umferðinni prepare mun lausnin þín vera í hlutverki aðstoðarmannsins. Í umferðinni play mun lausnin þín vera í hlutverki þín, töframannsins. Í báðum umferðum verður lausnin þín metin sem gagnvirkkeyrsla.

Undirbúningsumferð (Prepare Round)

Fyrsta línan í inntakinu inniheldur orðið prepare. Önnur línan inniheldur heiltölu $n$ ($2 \le n \le 500$) — fjölda hnúta. Næstu $(n - 1)$ línur innihalda hver um sig tvær heiltölur $u$ og $v$ ($1 \le u, v \le n$, $u < v$), sem tákna óstefndan legg milli $u$ og $v$ í trénu.

Þú verður að prenta eina línu sem inniheldur tvíundarunu $s$ af lengd nákvæmlega $(n - 1)$ sem samanstendur eingöngu af stöfunum 0 og 1. Þetta er strengurinn sem sendur er í seinni umferðina (play). Ef úttakið þitt fylgir ekki tilskildu sniði færðu dóminn Wrong Answer.

Leikumferð (Play Round)

Lausnin þín verður endurræst fyrir play umferðina.

Fyrsta línan inniheldur orðið play. Önnur línan inniheldur heiltöluna $n$. Þriðja línan inniheldur tvíundarununa $s$ nákvæmlega eins og þú prentaðir hana í prepare umferðinni.

Eftir það hefst leikurinn með $(n - 1)$ leikjum. Í hverjum leik verður gefin lína sem inniheldur tvær heiltölur $u$ og $v$ ($1 \le u, v \le n$, $u < v$). Sem svar ættirðu að prenta eina línu sem inniheldur annaðhvort take eða ignore. Allir leggir úr fyrri umferðinni verða gefnir nákvæmlega einu sinni, og röð leggjanna er valin jafndreift af handahófi úr $(n - 1)!$ mögulegum umröðunum.

Þegar úttak er á ógildu sniði lýkur leiknum samstundis án frekari upplýsinga frá samskiptaforritinu.

Mat á réttmæti

Látum $M$ vera mengi þeirra leggja sem lausnin þín velur. Það telst viðunandi ef enginn hnútur liggur að fleiri en einum völdum legg og $|M| = |M^*|$, þar sem $M^*$ er hámarkspörun netsins.

Það eru nákvæmlega $50$ próf, fyrir utan dæmaprófin. Til að standast verkefnið þarf lausnin þín að vera rétt á öllum prófunum, þar á meðal dæmaprófunum.

Tryggt er að allar stokkanir séu ákveðnar áður en úttak lausnarinnar berst. Slembnin er föst fyrir hvert próf, útfærð með því að festa fræ (seed) gervihandahófsgjafa.

Prófunartól fylgir með til að hjálpa þér að þróa og prófa lausnina þína.

Dæmi

Dæmi 1, Umferð 1

Inntak

prepare
3
1 2
1 3

Úttak

00

Dæmi 1, Umferð 2

Inntak

play
3
00
1 3

1 2

Úttak

take

ignore

Skýring á Dæmi 1

Þar sem $|M^*| = 1$ er viðunandi að taka hvaða legg sem er, og vísbendingin getur verið hvað sem er.