Beskrivning
Det finns en riktad graf med $n$ hörn numrerade från $1$ till $n$. För varje hörn $1 \le i \le n$ är utgraden för hörn $i$ högst ett; därmed kan vi beskriva grafen med en array $p_i$, där $p_i = 0$ om utgraden för hörn $i$ är noll, och annars $1 \le p_i \le n$, $p_i \ne i$, och det finns en riktad kant från $i$ till $p_i$. Det finns inga riktade cykler i grafen, så från vilket hörn $i$ som helst kommer vägen som bildas genom att upprepade gånger gå till nästa hörn längs riktade kanter till slut att sluta i ett hörn med utgrad noll.
Från början ligger en träbricka på ett av hörnen. När du klappar i händerna flyttas brickan till hörn $p_i$ om den befinner sig på ett hörn $i$ med $p_i$ skilt från noll; annars flyttas den inte. Du kan dock inte alls se var brickan är — den enda operationen du kan utföra är att välja en delmängd av hörn, placera brickan på ett av dina valda hörn, klappa i händerna ett antal gånger och observera om brickan slutar på ett av dina valda hörn. Till och med brickans startposition och antalet gånger du klappar i händerna väljs av en interaktor: du får bara välja delmängden av hörn och observera det maximala antalet gånger du kan klappa i händerna så att brickan kan starta på ett av dina valda hörn och sluta på ett av dina valda hörn.
Du vill lägga till en enda kant från $x$ till $y$ ($1 \le x, y \le n$, $x \ne y$ och $p_x = 0$, dvs. du kan sätta $p_x = y$), så att du kommer att kunna klappa i händerna ännu fler gånger på hela grafen än tidigare. Att lägga till kanten får dock inte skapa några riktade cykler i grafen.
Hitta en sådan kant som du kan lägga till genom att fråga efter det maximala antalet gånger du kan klappa i händerna på högst $n$ delmängder av hörn, eller avgör att det är omöjligt att lägga till en sådan kant.
Indata
Den första raden i indata innehåller ett enda heltal $n$ ($1 \le n \le 1000$).
Interaktion
För att ställa en fråga, skriv ut en enda rad på formen $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, där $1 \le k \le n$, och $1 \le u_i \le n$ är parvis olika hörn i din valda delmängd. Läs sedan en enda rad som innehåller ett enda heltal: det maximala antalet gånger du kan klappa i händerna så att brickan kan starta på ett av dina valda hörn och sluta på ett av dina valda hörn. Du får ställa högst $n$ frågor.
När du har bestämt vilken kant du vill lägga till, skriv ut en enda rad på formen $\texttt{! } x \text{ } y$, där $1 \le x, y \le n$ är ändpunkterna för den riktade kant du vill lägga till. Om det finns flera lösningar kan du skriva ut vilken som helst av dem.
Om det är omöjligt att lägga till en sådan kant, skriv ut $-1 \text{ -1}$ istället för kantens ändpunkter.
Din lösning måste avslutas omedelbart efter att svaret har skrivits ut.
Töm utdatabufferten (flush) efter varje fråga du ställer.
Interaktorn är inte adaptiv; grafen är fastställd i förväg.
Exempel
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
Notering
