Opis
Dany jest graf skierowany o $n$ wierzchołkach ponumerowanych od $1$ do $n$. Dla każdego wierzchołka $1 \le i \le n$, stopień wyjściowy wierzchołka $i$ wynosi co najwyżej jeden; możemy zatem opisać graf za pomocą tablicy $p_i$, gdzie $p_i = 0$, jeśli stopień wyjściowy wierzchołka $i$ wynosi zero, a w przeciwnym razie $1 \le p_i \le n$, $p_i \ne i$ oraz istnieje krawędź skierowana z $i$ do $p_i$. W grafie nie ma cykli skierowanych, więc z dowolnego wierzchołka $i$ ścieżka utworzona przez wielokrotne przechodzenie do następnego wierzchołka wzdłuż krawędzi skierowanych ostatecznie zakończy się w wierzchołku o stopniu wyjściowym równym zero.
Początkowo na jednym z wierzchołków znajduje się drewniany pionek. Kiedy klaśniesz w dłonie, jeśli pionek znajduje się na wierzchołku $i$ o niezerowym $p_i$, przesunie się on na wierzchołek $p_i$; w przeciwnym razie nie porusza się. Nie widzisz jednak, gdzie znajduje się pionek — jedyną operacją, jaką możesz wykonać, jest wybranie podzbioru wierzchołków, umieszczenie pionka na jednym z wybranych wierzchołków, klaśnięcie w dłonie pewną liczbę razy i zaobserwowanie, czy pionek zakończy ruch na jednym z wybranych przez ciebie wierzchołków. Nawet początkowe położenie pionka oraz liczba klaśnięć są wybierane przez interaktora: ty możesz jedynie wybrać podzbiór wierzchołków i zaobserwować maksymalną liczbę klaśnięć, przy której pionek może wystartować z jednego z wybranych wierzchołków i zakończyć ruch na jednym z wybranych wierzchołków.
Chciałbyś dodać pojedynczą krawędź z $x$ do $y$ ($1 \le x, y \le n$, $x \ne y$ oraz $p_x = 0$, tzn. możesz ustawić $p_x = y$), tak abyś mógł klasnąć w dłonie na całym grafie jeszcze więcej razy niż dotychczas. Dodanie tej krawędzi nie może jednak utworzyć żadnego cyklu skierowanego w grafie.
Znajdź dowolną taką krawędź, którą można dodać, pytając o maksymalną liczbę klaśnięć dla co najwyżej $n$ podzbiorów wierzchołków, lub stwierdź, że dodanie takiej krawędzi jest niemożliwe.
Wejście
Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 1000$).
Interakcja
Aby zadać zapytanie, wypisz pojedynczy wiersz w postaci $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, gdzie $1 \le k \le n$, a $1 \le u_i \le n$ to parami różne wierzchołki w wybranym podzbiorze. Następnie wczytaj pojedynczy wiersz zawierający jedną liczbę całkowitą: maksymalną liczbę klaśnięć w dłonie, przy której pionek może rozpocząć i zakończyć ruch na wierzchołkach z wybranego podzbioru. Możesz zadać co najwyżej $n$ zapytań.
Po ustaleniu krawędzi, którą chcesz dodać, wypisz pojedynczy wiersz w postaci $\texttt{! } x \text{ } y$, gdzie $1 \le x, y \le n$ to końce skierowanej krawędzi, którą chcesz dodać. Jeśli istnieje wiele rozwiązań, możesz wypisać dowolne z nich.
Jeśli dodanie takiej krawędzi jest niemożliwe, wypisz $-1 \text{ -1}$ zamiast końców krawędzi.
Twoje rozwiązanie musi zakończyć działanie natychmiast po wypisaniu odpowiedzi.
Opróżniaj bufor wyjścia (flush) po każdym zadanym zapytaniu.
Interaktor nie jest adaptacyjny; graf jest ustalony z góry.
Przykład
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
Uwaga
