Описание
Дан ориентированный граф на $n$ вершинах, пронумерованных от $1$ до $n$. Для каждой вершины $1 \le i \le n$ полустепень исхода вершины $i$ не превосходит единицы; таким образом, мы можем описать граф с помощью массива $p_i$, где $p_i = 0$, если полустепень исхода вершины $i$ равна нулю, а иначе $1 \le p_i \le n$, $p_i \ne i$, и существует ориентированное ребро из $i$ в $p_i$. В графе нет ориентированных циклов, поэтому из любой вершины $i$ путь, образованный последовательным переходом к следующей вершине по ориентированным рёбрам, в конечном счёте завершится в вершине с нулевой полустепенью исхода.
Изначально на одной из вершин стоит деревянная шашка. Когда вы хлопаете в ладоши, если шашка находится в вершине $i$ с ненулевым $p_i$, она перемещается в вершину $p_i$; в противном случае она остаётся на месте. Однако вы совершенно не видите, где находится шашка — единственная доступная вам операция состоит в том, чтобы выбрать подмножество вершин, поставить шашку на одну из выбранных вершин, хлопнуть в ладоши некоторое количество раз и увидеть, окажется ли шашка в итоге на одной из выбранных вершин. Даже начальное положение шашки и количество хлопков выбираются интерактором: вы можете лишь выбрать подмножество вершин и узнать максимальное количество хлопков, при котором шашка может начать движение в одной из выбранных вами вершин и закончить его в одной из выбранных вами вершин.
Вы хотите добавить одно ребро из $x$ в $y$ ($1 \le x, y \le n$, $x \ne y$ и $p_x = 0$, то есть можно положить $p_x = y$), чтобы на всём графе можно было хлопнуть в ладоши ещё больше раз, чем раньше. При этом добавление ребра не должно создавать ориентированных циклов в графе.
Найдите любое такое ребро, которое можно добавить, сделав запросы о максимальном количестве хлопков не более чем для $n$ подмножеств вершин, или определите, что добавить такое ребро невозможно.
Входные данные
Первая строка входных данных содержит одно целое число $n$ ($1 \le n \le 1000$).
Взаимодействие
Чтобы сделать запрос, выведите одну строку вида $\texttt{? } k \text{ } u_1 \text{ } u_2 \ldots u_k$, где $1 \le k \le n$, а $1 \le u_i \le n$ — попарно различные вершины в выбранном вами подмножестве. Затем считайте одну строку, содержащую одно целое число: максимальное количество раз, которое вы можете хлопнуть в ладоши так, чтобы шашка могла начать путь в одной из выбранных вершин и закончить его в одной из выбранных вершин. Вы можете сделать не более $n$ запросов.
После того как вы определили ребро, которое хотите добавить, выведите одну строку вида $\texttt{! } x \text{ } y$, где $1 \le x, y \le n$ — концы ориентированного ребра, которое вы хотите добавить. Если решений несколько, вы можете вывести любое из них.
Если добавить такое ребро невозможно, выведите $-1 \text{ -1}$ вместо концов ребра.
Ваше решение должно немедленно завершиться после вывода ответа.
Сбрасывайте буфер вывода (flush) после каждого сделанного запроса.
Интерактор не адаптивен; граф зафиксирован заранее.
Пример
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
Примечание
