Tämä on vuorovaikutteinen tehtävä.

Little Cyan Fishillä on piilotettu yksinkertainen suuntaamaton verkko, jossa on $n$ solmua, jotka on numeroitu luvuilla $1$ – $n$. Tiedät luvun $n$ arvon, mutta et tiedä yhtäkään verkon kaarta. Little Cyan Fish pitää kovasti leikkauksen (cut) käsitteestä. Olkoon solmujoukolle $S$ merkintä $\operatorname{cut}(S)$ niiden kaarten lukumäärä, joista täsmälleen toinen päätepiste kuuluu joukkoon $S$.

Little Cyan Fish antaa sinun vertailla leikkauksia tekemällä kyselyitä. Yhdessä kyselyssä valitset kaksi solmujoukkoa $S_1$ ja $S_2$. Little Cyan Fish kertoo sinulle, onko $\operatorname{cut}(S_1)$ pienempi, yhtä suuri vai suurempi kuin $\operatorname{cut}(S_2)$.

Voit luultavasti arvata, että seuraavaksi puhuttaisiin koko verkon selvittämisestä, mutta tällä kertaa tehtävä on helpompi. Little Cyan Fish antaa sinulle solmun $u$ ja haluaa sinun etsivän kaikki solmun $u$ naapurisolmut tekemällä korkeintaan $n + 10$ kyselyä.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $u$ ($1 \le n \le 1000$, $1 \le u \le n$), jotka ilmaisevat solmujen lukumäärän ja annetun solmun. Tämän jälkeen vuorovaikutus alkaa.

Vuorovaikutusprotokolla

Tehdäksesi kyselyn tulosta rivi seuraavassa muodossa:

$$?\ s_1\ s_2$$

missä $s_1$ ja $s_2$ ovat pituudeltaan $n$ olevia merkkijonoja, jotka koostuvat vain merkeistä 0 ja 1. Jokaisella $j \in \{1, 2\}$ solmu $i$ kuuluu joukkoon $S_j$ jos ja vain jos merkkijonon $s_j$ $i$:s merkki on 1. Joukot voivat olla tyhjiä, ne voivat mennä päällekkäin ja ne voivat olla samat.

Vastauksena kyselyyn saat yhden merkin <, = tai >, mikä tarkoittaa vastaavasti, että $\operatorname{cut}(S_1)$ on pienempi, yhtä suuri tai suurempi kuin $\operatorname{cut}(S_2)$. Sinun on varmistettava, että tekemiesi kyselyiden lukumäärä on korkeintaan $n + 10$.

Ilmoittaaksesi vastauksen tulosta rivi seuraavassa muodossa:

$$!\ k\ v_1\ v_2\ \dots\ v_k$$

missä $k$ ($0 \le k \le n - 1$) on solmun $u$ naapurisolmujen lukumäärä ja $v_1, v_2, \ldots, v_k$ ovat niiden erisuuret tunnisteet missä tahansa järjestyksessä. Jos $k = 0$, tulosta ! 0. Vastauksen ilmoittamista ei lasketa kyselyksi. Ohjelmasi täytyy päättyä välittömästi vastauksen ilmoittamisen jälkeen.

Tulostettuasi kyselyn tai ilmoitettuasi vastauksen älä unohda tulostaa rivinvaihtomerkkiä ja tyhjentää tulostuspuskuria (flush). Jos teet virheellisen kyselyn tai ylität kyselyrajan, tarkastin (interactor) sulkee syötevirran ja ohjelmasi täytyy päättyä.

Tässä tehtävässä tarkastin on mukautuva (adaptive). Tämä tarkoittaa, että verkko voi muuttua kyselyidesi perusteella, kunhan se ei ole ristiriidassa minkään aiemman vastauksen kanssa. Vastauksesi on oltava oikein jokaiselle verkolle, joka on yhdenmukainen kaikkien saamiesi vastausten kanssa.

Esimerkit

Syöte 1

4 1

<

=

<

=

Tuloste 1

? 0000 1000

? 0100 1100

? 0010 1010

? 0001 1001

! 2 2 4

Huomautus

Eräässä esimerkkivuorovaikutuksen kanssa yhdenmukaisessa verkossa on kaaret $(1, 2)$, $(1, 4)$ ja $(2, 3)$.

Testaustyökalu: Kilpailijoiden avuksi ratkaisujen kehittämiseen ja testaamiseen tarjotaan testaustyökalu. Voit ladata tämän työkalun liitteistä. Suorita työkalu valitsimella -h nähdäksesi käyttöohjeet. Työkalu tarkistaa vuorovaikutuksen ja ilmoitetun vastauksen, mutta ei valvo aika- tai muistirajaa.

Testaustyökalu käyttää koko vuorovaikutuksen ajan syötetiedostossaan määriteltyä kiinteää verkkoa, kun taas virallinen tarkastin on mukautuva. Testien läpäiseminen testaustyökalulla ei takaa, että ratkaisusi toimii oikein virallista tarkastinta vastaan.