Problembeskrivning
Självklart är detta ett problem.
Detta är ett interaktivt problem. Du får en okänd oriktad graf med $n$ hörn och $m$ kanter, utan multipelkanter eller öglor. Varje gång kan du ställa följande fråga till interaktionsbiblioteket:
- Givet en hörnmängd $S \subseteq \{1, 2, \dots, n\}$, fråga om denna hörnmängd är en oberoende mängd.
Här betyder en oberoende mängd att det inte finns någon kant mellan några två skilda hörn i mängden $S$.
Ditt mål är att bestämma hela kantmängden i grafen med högst $M = n + m(2 + \lceil\log_2 n\rceil)$ frågor.
Observera att du inte känner till värdet på $m$ i förväg, och att interaktionsbiblioteket är adaptivt, dvs. grafen är inte låst från början utan justeras dynamiskt utifrån dina frågor.
Indata
Den första raden innehåller ett heltal $T$ ($1 \le T \le 100$), som anger antalet testfall.
För varje testfall innehåller en rad ett heltal $n$ ($1 \le n \le 500$), som anger antalet hörn i den okända oriktade grafen.
Det garanteras att summan av $n$ över alla testfall inte överstiger $500$, $0 \le m \le 500$, och att summan av $m$ inte överstiger $500$.
Interaktion
När du behöver ställa en fråga, skriv ut en rad:
? k v_1 v_2 ... v_k
där $k$ anger storleken på hörnmängden, och $v_1, v_2, \dots, v_k$ är indexen för hörnen i mängden du frågar om, alla parvis olika.
Interaktionsbiblioteket returnerar ett heltal: $1$ om hörnmängden är en oberoende mängd; $0$ annars.
När du har bestämt alla kanter i grafen, skriv ut en rad:
! m u_1 v_1 u_2 v_2 ... u_m v_m
där $m$ är antalet kanter i den oriktade grafen, och $(u_i, v_i)$ representerar en kant i grafen. Du kan skriva ut kanterna i valfri ordning.
Därefter, om det inte finns några återstående testfall, måste ditt program avslutas omedelbart; annars ska det gå vidare till nästa testfall.
Exempel
Indata 1
1 4 0 1 0 0 1 0
Utdata 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
Notering
Exemplet visar en interaktiv process där man frågar om varje kant existerar individuellt.