Beskrivelse
Det finnes en rettet graf med $n$ noder nummerert fra $1$ til $n$. For hver node $1 \le i \le n$ er utgraden til node $i$ høyst én; dermed kan vi beskrive grafen ved hjelp av en tabell $p_i$, der $p_i = 0$ hvis utgraden til node $i$ er null, og ellers $1 \le p_i \le n$, $p_i \ne i$, og det går en rettet kant fra $i$ til $p_i$. Det er ingen rettede sykler i grafen, så fra enhver node $i$ vil stien som dannes ved å gjentatte ganger gå til neste node langs rettede kanter til slutt ende i en node med utgrad null.
Til å begynne med ligger det en trebrikke på en av nodene. Når du klapper i hendene, vil brikken flytte seg til node $p_i$ dersom den står på en node $i$ med $p_i$ ulik null; ellers flytter den seg ikke. Du kan imidlertid overhodet ikke se hvor brikken er — den eneste operasjonen du kan utføre er å velge en delmengde av noder, plassere brikken på en av dine valgte noder, klappe i hendene et visst antall ganger, og observere om brikken ender opp på en av dine valgte noder. Til og med brikkens startposisjon og antallet ganger du klapper i hendene velges av en interaktor: du får bare velge delmengden av noder, og observere det maksimale antallet ganger du kan klappe i hendene slik at brikken kan starte på en av dine valgte noder og ende på en av dine valgte noder.
Du ønsker å legge til én enkelt kant fra $x$ til $y$ ($1 \le x, y \le n$, $x \ne y$ og $p_x = 0$, dvs. at du kan sette $p_x = y$), slik at du kan klappe i hendene enda flere ganger på hele grafen enn før. Likevel må det å legge til kanten ikke skape noen rettede sykler i grafen.
Finn en hvilken som helst slik kant du kan legge til ved å spørre om det maksimale antallet ganger du kan klappe i hendene på høyst $n$ delmengder av noder, eller avgjør at det er umulig å legge til en slik kant.
Inndata
Den første linjen i inndata inneholder et enkelt heltall $n$ ($1 \le n \le 1000$).
Interaksjon
For å stille et spørsmål, skriv ut én enkelt linje på formen $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, der $1 \le k \le n$, og $1 \le u_i \le n$ er parvis forskjellige noder i din valgte delmengde. Les deretter én enkelt linje som inneholder et enkelt heltall: det maksimale antallet ganger du kan klappe i hendene slik at brikken kan starte på en av dine valgte noder og ende på en av dine valgte noder. Du kan stille høyst $n$ spørsmål.
Etter at du har bestemt hvilken kant du vil legge til, skriv ut én enkelt linje på formen $\texttt{! } x \text{ } y$, der $1 \le x, y \le n$ er endepunktene til den rettede kanten du vil legge til. Hvis det finnes flere løsninger, kan du skrive ut hvilken som helst av dem.
Hvis det er umulig å legge til en slik kant, skriv ut $-1 \text{ -1}$ i stedet for endepunktene til kanten.
Løsningen din må avsluttes umiddelbart etter at svaret er skrevet ut.
Tøm utdatabufferen (flush) etter hvert spørsmål du stiller.
Interaktoren er ikke adaptiv; grafen er fastsatt på forhånd.
Eksempel
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
Merk
