문제 설명
$n$개의 정점으로 이루어진 방향 그래프가 있으며, 정점에는 $1$부터 $n$까지 번호가 매겨져 있습니다. 각 정점 $1 \le i \le n$에 대해, 정점 $i$의 진출 차수는 최대 1입니다. 따라서 이 그래프는 배열 $p_i$를 사용하여 나타낼 수 있는데, 정점 $i$의 진출 차수가 0이면 $p_i = 0$이고, 그렇지 않으면 $1 \le p_i \le n$, $p_i \ne i$이며 정점 $i$에서 정점 $p_i$로 가는 방향 간선이 존재합니다. 그래프에는 방향 사이클이 없으므로, 임의의 정점 $i$에서 출발하여 방향 간선을 따라 다음 정점으로 계속 이동하면 결국 진출 차수가 0인 정점에서 멈추게 됩니다.
처음에 정점 중 하나에 나무 체커(말)가 놓여 있습니다. 당신이 박수를 치면, 체커가 있는 정점 $i$의 $p_i$가 0이 아닐 때 체커는 정점 $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$번까지 할 수 있습니다.
추가하고 싶은 간선을 찾았다면, 추가할 방향 간선의 두 끝점 $1 \le x, y \le n$에 대해 $\texttt{! } x \text{ } y$ 형태의 한 줄을 출력하세요. 가능한 답이 여러 개라면 그중 아무것이나 출력해도 됩니다.
그러한 간선을 추가하는 것이 불가능하다면, 간선의 끝점 대신 $-1 \text{ -1}$을 출력하세요.
답을 출력한 직후 프로그램은 즉시 종료되어야 합니다.
각 질의를 출력한 후에는 출력 버퍼를 비워야(flush) 합니다.
인터랙터는 적응형(adaptive)이 아니며, 그래프는 사전에 고정되어 있습니다.
예제
6
2
1
2
? 4 1 2 3 4
? 2 5 6
? 3 4 5 6
! 5 1
노트
