Descrizione
Certo, questo è un problema.
Questo è un problema interattivo. Ti viene dato un grafo non orientato sconosciuto con $n$ vertici e $m$ archi, senza archi multipli né cappi. Ogni volta puoi porre alla libreria di interazione la seguente domanda:
- Dato un insieme di vertici $S \subseteq \{1, 2, \dots, n\}$, chiedi se questo insieme di vertici è un insieme indipendente.
Qui, insieme indipendente significa che non c'è alcun arco tra due vertici distinti qualsiasi nell'insieme $S$.
Il tuo obiettivo è determinare l'intero insieme di archi del grafo usando non più di $M = n + m(2 + \lceil\log_2 n\rceil)$ interrogazioni.
Nota che non conosci il valore di $m$ in anticipo e la libreria di interazione è adattiva, cioè il grafo non è fissato fin dall'inizio, ma verrà adattato dinamicamente in base alle tue interrogazioni.
Input
La prima riga contiene un intero $T$ ($1 \le T \le 100$), che indica il numero di casi di test.
Per ogni caso di test, una riga contiene un intero $n$ ($1 \le n \le 500$), che indica il numero di vertici del grafo non orientato sconosciuto.
È garantito che la somma di $n$ su tutti i casi di test non supera $500$, $0 \le m \le 500$ e la somma di $m$ non supera $500$.
Interazione
Quando devi effettuare un'interrogazione, stampa una riga:
? k v_1 v_2 ... v_k
dove $k$ indica la dimensione dell'insieme di vertici e $v_1, v_2, \dots, v_k$ sono gli indici dei vertici nell'insieme che stai interrogando, tutti distinti a due a due.
La libreria di interazione restituirà un intero: $1$ se l'insieme di vertici è un insieme indipendente; $0$ altrimenti.
Quando hai determinato tutti gli archi del grafo, stampa una riga:
! m u_1 v_1 u_2 v_2 ... u_m v_m
dove $m$ è il numero di archi nel grafo non orientato e $(u_i, v_i)$ rappresenta un arco nel grafo. Puoi stampare gli archi in qualsiasi ordine.
Dopodiché, se non ci sono altri casi di test, il tuo programma deve terminare immediatamente; altrimenti deve procedere al caso di test successivo.
Esempi
Input 1
1 4 0 1 0 0 1 0
Output 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
Note
L'esempio mostra un processo interattivo in cui si chiede singolarmente se ciascun arco esiste.