Sunbath

题目描述

This is an interactive problem.

There is a hidden tournament $G$ on $n$ vertices numbered from $1$ to $n$.

A tournament is a directed graph such that for every pair of distinct vertices $u$ and $v$, exactly one of the two directed edges $(u,v)$ and $(v,u)$ exists.

You may ask the interactor two non-empty disjoint sets of vertices $A$ and $B$. The interactor will return the number of directed edges from $A$ to $B$.

Your task is to find a set of vertices $K$ such that $|K| \le \lceil \log_2 n \rceil + 1$, and for every vertex $v \notin K$, there exists a vertex $u \in K$ such that $(u,v)$ is an edge of $G$.

You have to find such a set $K$ using no more than $2n+150$ queries.

输入格式

First, read an integer $T$ ($1 \le T \le 100$), denoting the number of test cases.

For each test case, first read an integer $n$ ($1 \le n \le 2000$), denoting the number of vertices in the hidden tournament.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

The interactor may be adaptive. However, for each test case, all answers are guaranteed to be consistent with at least one tournament on the current $n$ vertices.

输出格式

To ask a query with two non-empty disjoint sets $A=\{a_1,a_2,\ldots,a_p\}$ and $B=\{b_1,b_2,\ldots,b_q\}$, output:

$? \space p \space a_1 \space a_2 \space \ldots \space a_p \space q \space b_1 \space b_2 \space \ldots \space b_q$

Here $1 \le p,q \le n$, all vertices in $A$ and $B$ must be distinct, and $A \cap B = \varnothing$.

Then you should read an integer $s$, denoting the number of ordered pairs $(a,b)$ such that $a \in A$, $b \in B$, and $(a,b)$ is an edge of $G$.

For each test case, the number of queries must not exceed $2n+150$.

When you have found a valid set $K=\{k_1,k_2,\ldots,k_m\}$ for the current test case, output:

$! \space m \space k_1 \space k_2 \space \ldots \space k_m$

Here $1 \le m \le \lceil \log_2 n \rceil + 1$.

After outputting the answer, you should continue to the next test case.

样例输入 #1

1
4

4

样例输出 #1

? 2 1 2 2 3 4

! 2 1 2