Descripción
Hay un grafo dirigido de $n$ vértices numerados del $1$ al $n$. Para cada vértice $1 \le i \le n$, el grado de salida del vértice $i$ es a lo sumo uno; por lo tanto, podemos describir el grafo mediante un arreglo $p_i$, donde $p_i = 0$ si el grado de salida del vértice $i$ es cero, y en caso contrario $1 \le p_i \le n$, $p_i \ne i$, y existe una arista dirigida de $i$ a $p_i$. No hay ciclos dirigidos en el grafo, por lo que desde cualquier vértice $i$, el camino formado al avanzar repetidamente al siguiente vértice a lo largo de las aristas dirigidas terminará finalmente en un vértice con grado de salida cero.
Inicialmente, hay una ficha de madera en uno de los vértices. Cuando das una palmada, si la ficha está en un vértice $i$ con $p_i$ distinto de cero, se moverá al vértice $p_i$; de lo contrario, no se mueve. Sin embargo, no puedes ver dónde está la ficha en absoluto: la única operación que puedes realizar es elegir un subconjunto de vértices, colocar la ficha en uno de los vértices elegidos, dar palmadas un cierto número de veces y observar si la ficha termina en uno de los vértices elegidos. Incluso la posición inicial de la ficha y el número de veces que das palmadas son elegidos por el interactor: tú solo puedes elegir el subconjunto de vértices y observar el número máximo de veces que puedes dar palmadas de modo que la ficha pueda comenzar en uno de tus vértices elegidos y terminar en uno de tus vértices elegidos.
Te gustaría añadir una única arista de $x$ a $y$ ($1 \le x, y \le n$, $x \ne y$, y $p_x = 0$, es decir, puedes asignar $p_x = y$), de manera que puedas dar palmadas aún más veces en todo el grafo que antes. Aun así, añadir la arista no puede crear ningún ciclo dirigido en el grafo.
Encuentra cualquier arista de este tipo que puedas añadir consultando el número máximo de veces que puedes dar palmadas en a lo sumo $n$ subconjuntos de vértices, o determina que es imposible añadir dicha arista.
Entrada
La primera línea de la entrada contiene un único entero $n$ ($1 \le n \le 1000$).
Interacción
Para hacer una consulta, imprime una sola línea de la forma $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, donde $1 \le k \le n$, y $1 \le u_i \le n$ son vértices distintos dos a dos en tu subconjunto elegido. Luego lee una sola línea que contiene un único entero: el número máximo de veces que puedes dar palmadas de modo que la ficha pueda comenzar en uno de tus vértices elegidos y terminar en uno de tus vértices elegidos. Puedes hacer a lo sumo $n$ consultas.
Después de haber determinado la arista que deseas añadir, imprime una sola línea de la forma $\texttt{! } x \text{ } y$, donde $1 \le x, y \le n$ son los extremos de la arista dirigida que deseas añadir. Si hay múltiples soluciones, puedes imprimir cualquiera de ellas.
Si es imposible añadir dicha arista, imprime $-1 \text{ -1}$ en lugar de los extremos de la arista.
Tu solución debe terminar inmediatamente después de imprimir la respuesta.
Vacía el búfer de salida (flush) después de cada consulta que realices.
El interactor no es adaptativo; el grafo está fijado de antemano.
Ejemplo
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
Nota
