Descripción
Por supuesto, esto es un problema.
Este es un problema interactivo. Se te da un grafo no dirigido desconocido con $n$ vértices y $m$ aristas, sin aristas múltiples ni bucles. Cada vez, puedes hacer la siguiente pregunta a la biblioteca de interacción:
- Dado un conjunto de vértices $S \subseteq \{1, 2, \dots, n\}$, preguntar si este conjunto de vértices es un conjunto independiente.
Aquí, un conjunto independiente significa que no hay ninguna arista entre dos vértices distintos cualesquiera en el conjunto $S$.
Tu objetivo es determinar todo el conjunto de aristas del grafo utilizando no más de $M = n + m(2 + \lceil\log_2 n\rceil)$ consultas.
Ten en cuenta que no conoces el valor de $m$ de antemano, y la biblioteca de interacción es adaptativa, es decir, el grafo no está fijo desde el principio, sino que se ajustará dinámicamente según tus consultas.
Entrada
La primera línea contiene un entero $T$ ($1 \le T \le 100$), que denota el número de casos de prueba.
Para cada caso de prueba, una línea contiene un entero $n$ ($1 \le n \le 500$), que denota el número de vértices del grafo no dirigido desconocido.
Se garantiza que la suma de $n$ en todos los casos de prueba no supera $500$, $0 \le m \le 500$, y la suma de $m$ no supera $500$.
Interacción
Cuando necesites hacer una consulta, imprime una línea:
? k v_1 v_2 ... v_k
donde $k$ denota el tamaño del conjunto de vértices, y $v_1, v_2, \dots, v_k$ son los índices de los vértices en el conjunto que estás consultando, todos distintos entre sí.
La biblioteca de interacción devolverá un entero: $1$ si el conjunto de vértices es un conjunto independiente; $0$ en caso contrario.
Cuando hayas determinado todas las aristas del grafo, imprime una línea:
! m u_1 v_1 u_2 v_2 ... u_m v_m
donde $m$ es el número de aristas en el grafo no dirigido, y $(u_i, v_i)$ representa una arista en el grafo. Puedes imprimir las aristas en cualquier orden.
Después de eso, si no quedan casos de prueba, tu programa debe terminar inmediatamente; de lo contrario, debe proceder al siguiente caso de prueba.
Ejemplos
Entrada 1
1 4 0 1 0 0 1 0
Salida 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
Nota
El ejemplo demuestra un proceso interactivo en el que se consulta individualmente si existe cada arista.