Tehtävänanto
Tietenkin tämä on tehtävä.
Tämä on vuorovaikutteinen tehtävä. Sinulle annetaan tuntematon suuntaamaton verkko, jossa on $n$ solmua ja $m$ kaarta, eikä siinä ole moninkertaisia kaaria tai silmukoita. Joka kerta voit esittää vuorovaikutuskirjastolle seuraavan kysymyksen:
- Annettuna solmujoukko $S \subseteq \{1, 2, \dots, n\}$, kysy, onko tämä solmujoukko riippumaton joukko.
Tässä riippumaton joukko tarkoittaa, että minkään kahden joukon $S$ eri solmun välillä ei ole kaarta.
Tavoitteenasi on määrittää verkon koko kaarijoukko käyttäen enintään $M = n + m(2 + \lceil\log_2 n\rceil)$ kyselyä.
Huomaa, että et tiedä luvun $m$ arvoa etukäteen, ja vuorovaikutuskirjasto on mukautuva (adaptive), eli verkkoa ei ole kiinnitetty alussa, vaan sitä mukautetaan dynaamisesti kyselyidesi perusteella.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 100$), joka ilmaisee testitapausten lukumäärän.
Jokaista testitapausta kohden yhdellä rivillä on kokonaisluku $n$ ($1 \le n \le 500$), joka ilmaisee tuntemattoman suuntaamattoman verkon solmujen lukumäärän.
On taattu, että lukujen $n$ summa kaikissa testitapauksissa on enintään $500$, $0 \le m \le 500$ ja lukujen $m$ summa on enintään $500$.
Vuorovaikutus
Kun haluat tehdä kyselyn, tulosta yksi rivi:
? k v_1 v_2 ... v_k
missä $k$ tarkoittaa solmujoukon kokoa ja $v_1, v_2, \dots, v_k$ ovat kyseltävän joukon solmujen indeksit, kaikki pareittain eri suuria.
Vuorovaikutuskirjasto palauttaa kokonaisluvun: $1$, jos solmujoukko on riippumaton joukko; muulloin $0$.
Kun olet määrittänyt verkon kaikki kaaret, tulosta yksi rivi:
! m u_1 v_1 u_2 v_2 ... u_m v_m
missä $m$ on suuntaamattoman verkon kaarten lukumäärä ja $(u_i, v_i)$ esittää verkon kaarta. Voit tulostaa kaaret missä tahansa järjestyksessä.
Tämän jälkeen, jos testitapauksia ei ole enää jäljellä, ohjelmasi on päätyttävä välittömästi; muussa tapauksessa sen tulee siirtyä seuraavaan testitapaukseen.
Esimerkit
Syöte 1
1 4 0 1 0 0 1 0
Tuloste 1
? 2 1 2 ? 2 1 3 ? 2 1 4 ? 2 2 3 ? 2 2 4 ? 2 3 4 ! 4 1 2 2 3 3 4 1 4
Huomautus
Esimerkki havainnollistaa vuorovaikutteista prosessia, jossa kysytään erikseen kunkin kaaren olemassaoloa.