Este problema es interactivo.
Hemos ocultado un grafo no dirigido $G$ con $n$ vértices. Se garantiza que es conexo y que no contiene aristas múltiples ni bucles.
Puedes realizar hasta 60 consultas de la siguiente forma:
- Considera un subconjunto $S$ del conjunto de vértices de $G$. ¿Cuántas aristas hay en el subgrafo inducido por $S$? En otras palabras, ¿cuántas aristas de $G$ tienen ambos extremos en $S$?
Tu objetivo es determinar si existe un ciclo euleriano en este grafo. Un ciclo euleriano es un recorrido del grafo que pasa por cada arista exactamente una vez y empieza y termina en el mismo vértice.
Ten en cuenta que el grafo $G$ queda fijado antes del inicio de la interacción. En otras palabras, el interactor no es adaptativo.
Entrada
La primera línea contiene un entero $n$ ($3 \le n \le 10^4$), el número de vértices de $G$. Se garantiza que $G$ tiene como máximo $10^5$ aristas, es conexo y no contiene aristas múltiples ni bucles.
Interacción
Comienza la interacción leyendo una línea con el entero $n$.
Para conocer el número de aristas del subgrafo de $G$ inducido por $k$ vértices $x_1,x_2,\ldots,x_k$, imprime una línea con el formato ? k x1 x2 ... xk ($0 \le k \le n$, $1 \le x_i \le n$, todos los $x_i$ son distintos).
Como respuesta, el programa del jurado imprimirá una línea con un entero $m$: el número de tales aristas.
Si tu consulta no es válida o realizas más de 60 consultas, el programa del jurado imprimirá $-1$ y finalizará la interacción. Recibirás el resultado «Respuesta incorrecta». Asegúrate de terminar tu programa inmediatamente para evitar otros resultados.
Cuando hayas determinado si el grafo contiene un ciclo euleriano, imprime una sola línea: ! YES si existe dicho ciclo, y ! NO si no existe.
Después de imprimir cada línea, no olvides imprimir el fin de línea y vaciar el búfer de salida. De lo contrario, recibirás el resultado «Límite de inactividad excedido».
Ejemplos
Entrada 1
3 1 0
Salida 1
? 2 1 2 ? 2 1 3 ! NO
Nota
El grafo oculto del ejemplo tiene $3$ vértices y las aristas $(2,1)$ y $(2,3)$.