Kuvaus
Annettuna on suunnattu verkko, jossa on $n$ solmua numeroituina $1$:stä $n$:ään. Jokaiselle solmulle $1 \le i \le n$ solmun $i$ lähtöaste on enintään yksi; niinpä voimme kuvata verkon taulukolla $p_i$, missä $p_i = 0$, jos solmun $i$ lähtöaste on nolla, ja muulloin $1 \le p_i \le n$, $p_i \ne i$ ja solmusta $i$ solmuun $p_i$ on suunnattu kaari. Verkossa ei ole suunnattuja syklejä, joten mistä tahansa solmusta $i$ polku, joka muodostuu siirtymällä toistuvasti seuraavaan solmuun suunnattuja kaaria pitkin, päättyy lopulta solmuun, jonka lähtöaste on nolla.
Aluksi yhdessä solmuista on puinen pelinappula. Kun taputat käsiäsi, jos nappula on solmussa $i$, jolle $p_i$ on nollasta poikkeava, se siirtyy solmuun $p_i$; muuten se ei liiku. Et kuitenkaan lainkaan näe, missä nappula on — ainoa toimenpide, jonka voit tehdä, on valita solmujen osajoukko, asettaa nappula johonkin valitsemistasi solmuista, taputtaa käsiäsi tietyn määrän kertoja ja havainnoida, päätyykö nappula johonkin valitsemistasi solmuista. Jopa nappulan alkusijainnin ja taputusten määrän valitsee interaktori: sinä saat vain valita solmujen osajoukon ja havainnoida suurimman mahdollisen taputusmäärän, jolla nappula voi aloittaa jostakin valitsemastasi solmusta ja päätyä johonkin valitsemaasi solmuun.
Haluaisit lisätä yhden kaaren solmusta $x$ solmuun $y$ ($1 \le x, y \le n$, $x \ne y$ ja $p_x = 0$, eli voit asettaa $p_x = y$), jotta voisit taputtaa käsiäsi koko verkossa vielä useammin kuin aiemmin. Kaaren lisääminen ei kuitenkaan saa muodostaa verkkoon yhtäkään suunnattua sykliä.
Etsi mikä tahansa tällainen lisättävä kaari kysymällä suurinta mahdollista taputusmäärää enintään $n$:lle solmujen osajoukolle, tai päätä, että tällaisen kaaren lisääminen on mahdotonta.
Syöte
Syötteen ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 1000$).
Vuorovaikutus
Tehdäksesi kyselyn tulosta yksi rivi muotoa $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, missä $1 \le k \le n$ ja $1 \le u_i \le n$ ovat pareittain eri solmuja valitsemassasi osajoukossa. Lue sitten yksi rivi, joka sisältää yhden kokonaisluvun: suurimman määrän kertoja, jonka voit taputtaa käsiäsi niin, että nappula voi aloittaa jostakin valitsemastasi solmusta ja päätyä johonkin valitsemaasi solmuun. Voit tehdä enintään $n$ kyselyä.
Kun olet selvittänyt kaaren, jonka haluat lisätä, tulosta yksi rivi muotoa $\texttt{! } x \text{ } y$, missä $1 \le x, y \le n$ ovat lisättävän suunnatun kaaren päätepisteet. Jos ratkaisuja on useita, voit tulostaa niistä minkä tahansa.
Jos tällaisen kaaren lisääminen on mahdotonta, tulosta $-1 \text{ -1}$ kaaren päätepisteiden sijaan.
Ratkaisusi on lopetettava suoritus välittömästi vastauksen tulostamisen jälkeen.
Tyhjennä tulostuspuskuri (flush) jokaisen tekemäsi kyselyn jälkeen.
Interaktori ei ole mukautuva; verkko on kiinnitetty etukäteen.
Esimerkki
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
Huomautus
