문제 설명
물론, 이것은 문제입니다.
이 문제는 인터랙티브 문제입니다. $n$개의 정점과 $m$개의 간선으로 이루어진 알 수 없는 무방향 그래프가 주어지며, 다중 간선이나 자기 루프는 없습니다. 매번 인터랙션 라이브러리에 다음과 같은 질문을 할 수 있습니다:
- 정점 집합 $S \subseteq \{1, 2, \dots, n\}$이 주어졌을 때, 이 정점 집합이 독립 집합인지 질문합니다.
여기서 독립 집합이란 집합 $S$에 속한 임의의 서로 다른 두 정점 사이에 간선이 존재하지 않음을 의미합니다.
당신의 목표는 최대 $M = n + m(2 + \lceil\log_2 n\rceil)$번의 질문만을 사용하여 그래프의 전체 간선 집합을 알아내는 것입니다.
사전에 $m$의 값을 알 수 없으며, 인터랙션 라이브러리는 적응형(adaptive)이라는 점에 유의하세요. 즉, 그래프가 처음부터 고정되어 있지 않고 당신의 질문에 따라 동적으로 조정됩니다.
입력
첫째 줄에 테스트 케이스의 개수를 나타내는 정수 $T$ ($1 \le T \le 100$)가 주어집니다.
각 테스트 케이스마다 한 줄에 알 수 없는 무방향 그래프의 정점 개수를 나타내는 정수 $n$ ($1 \le n \le 500$)이 주어집니다.
모든 테스트 케이스에서 $n$의 합은 $500$을 넘지 않으며, $0 \le m \le 500$이고, $m$의 합도 $500$을 넘지 않음이 보장됩니다.
상호작용
질문을 해야 할 때는 한 줄을 출력합니다:
? k v_1 v_2 ... v_k
여기서 $k$는 정점 집합의 크기를 나타내며, $v_1, v_2, \dots, v_k$는 질문하려는 집합에 속한 정점들의 번호로, 모두 서로 달라야 합니다.
인터랙션 라이브러리는 정수를 반환합니다: 정점 집합이 독립 집합이면 $1$, 그렇지 않으면 $0$입니다.
그래프의 모든 간선을 알아냈다면 한 줄을 출력합니다:
! m u_1 v_1 u_2 v_2 ... u_m v_m
여기서 $m$은 무방향 그래프의 간선 개수이고, $(u_i, v_i)$는 그래프의 한 간선을 나타냅니다. 간선들은 어떤 순서로 출력해도 됩니다.
그 후 남은 테스트 케이스가 없다면 프로그램은 즉시 종료되어야 하며, 그렇지 않다면 다음 테스트 케이스를 계속 진행해야 합니다.
예제
예제 입력 1
1 4 0 1 0 0 1 0
예제 출력 1
? 2 1 2 ? 2 1 3 ? 2 1 4 ? 2 2 3 ? 2 2 4 ? 2 3 4 ! 4 1 2 2 3 3 4 1 4
힌트
예제는 각 간선이 존재하는지 개별적으로 질문하는 상호작용 과정을 보여줍니다.