Descrizione
C'è un grafo orientato su $n$ vertici numerati da $1$ a $n$. Per ogni vertice $1 \le i \le n$, il grado uscente del vertice $i$ è al massimo uno; pertanto possiamo descrivere il grafo usando un array $p_i$, dove $p_i = 0$ se il grado uscente del vertice $i$ è zero, e altrimenti $1 \le p_i \le n$, $p_i \ne i$, ed esiste un arco orientato da $i$ a $p_i$. Non ci sono cicli orientati nel grafo, quindi da qualsiasi vertice $i$, il cammino formato spostandosi ripetutamente al vertice successivo lungo gli archi orientati terminerà infine in un vertice con grado uscente zero.
Inizialmente, c'è una pedina di legno su uno dei vertici. Quando batti le mani, se la pedina si trova su un vertice $i$ con $p_i$ diverso da zero, si sposterà sul vertice $p_i$; altrimenti non si muove. Tuttavia, non puoi vedere affatto dove si trovi la pedina — l'unica operazione che puoi compiere è scegliere un sottoinsieme di vertici, posizionare la pedina su uno dei vertici scelti, battere le mani un certo numero di volte e osservare se la pedina finisce su uno dei vertici da te scelti. Persino il posizionamento iniziale della pedina e il numero di battiti di mani sono scelti da un interattore: tu puoi solo scegliere il sottoinsieme di vertici e osservare il numero massimo di volte in cui puoi battere le mani affinché la pedina possa partire da uno dei vertici scelti e terminare su uno dei vertici scelti.
Vorresti aggiungere un singolo arco da $x$ a $y$ ($1 \le x, y \le n$, $x \ne y$ e $p_x = 0$, cioè puoi impostare $p_x = y$), in modo da poter battere le mani ancora più volte sull'intero grafo rispetto a prima. Tuttavia, l'aggiunta dell'arco non deve creare alcun ciclo orientato nel grafo.
Trova un qualsiasi arco di questo tipo che puoi aggiungere interrogando il numero massimo di battiti di mani su al più $n$ sottoinsiemi di vertici, oppure determina che è impossibile aggiungere un tale arco.
Input
La prima riga dell'input contiene un singolo intero $n$ ($1 \le n \le 1000$).
Interazione
Per effettuare una query, stampa una singola riga della forma $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, dove $1 \le k \le n$, e $1 \le u_i \le n$ sono vertici a due a due distinti nel sottoinsieme scelto. Poi leggi una singola riga contenente un singolo intero: il numero massimo di volte in cui puoi battere le mani affinché la pedina possa partire da uno dei vertici scelti e terminare su uno dei vertici scelti. Puoi effettuare al massimo $n$ query.
Dopo aver determinato l'arco che desideri aggiungere, stampa una singola riga della forma $\texttt{! } x \text{ } y$, dove $1 \le x, y \le n$ sono gli estremi dell'arco orientato che desideri aggiungere. Se esistono più soluzioni, puoi stamparne una qualsiasi.
Se è impossibile aggiungere un tale arco, stampa $-1 \text{ -1}$ al posto degli estremi dell'arco.
La tua soluzione deve terminare immediatamente dopo aver stampato la risposta.
Svuota il buffer di output (flush) dopo ogni query effettuata.
L'interattore non è adattivo; il grafo è fissato in anticipo.
Esempio
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
Note
