No.3591 I Love Graph
Problem Statement
This is an interactive problem (your program and the judge system communicate through standard input and output).
In a galaxy far, far away, there are $N$ space stations, numbered from $1$ to $N$. Some pairs of these stations are connected by bidirectional "transparent wormholes". Because the star chart data has been completely lost, we know only the number of space stations $N$, and we know nothing about the connections, such as the total number of wormholes $M$ or which stations each wormhole connects. However, it is known that the total number of wormholes $M$ does not exceed $400$.
To restore the star chart, you can test by sending queries to the system's "gravitational wave detector". In one query, you specify and send two disjoint (having no elements in common) sets of space stations $A$ and $B$. The judge system immediately activates the detector and returns whether there exists at least $1$ wormhole directly connecting some station in set $A$ with some station in set $B$.
Determine all pairs of stations connected by wormholes using as few queries as possible.
Input and Output
First, the number of space stations $N$ is given from standard input.
$N$
Then, your program can send queries to the gravitational wave detector. Output each query to standard output in the following format.
? $K_A\ K_B\ A_1\ A_2\ \cdots \ A_{K_A}\ B_1\ B_2\ B_{K_B}$
Here, $K_A, K_B$ are the numbers of elements of the specified sets $A, B$ respectively, and must be integers satisfying $K_A \ge 1$ and $K_B \ge 1$. Also, $A$ represents the set $\{A_1, A_2, \dots, A_{K_A}\}$ consisting of $K_A$ stations, and $B$ represents the set $\{B_1, B_2, \dots, B_{K_B}\}$ consisting of $K_B$ stations. The specified station numbers must be pairwise distinct integers satisfying $1 \le A_i, B_j \le N$, and the two sets must not contain a common station ($A \cap B = \emptyset$).
After you send a query, the result $R$ is given from the judge system to standard input.
$R$
- When $R = 1$: there exists at least one wormhole between set $A$ and set $B$.
- When $R = 0$: there are no wormholes between set $A$ and set $B$.
- When $R = -1$: this is given when the format of the sent query was incorrect or when the query limit was exceeded. In this case, terminate your program immediately. Otherwise, the judge result is undefined.
Once you have determined all the connections, output your answer in the following format and terminate your program normally. Outputting the answer does not count toward the number of queries.
! $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$
Here, $M$ is the total number of existing wormholes, and $u_m, v_m$ are the numbers of the stations connected by the $m\ (1 \le m \le M)$-th wormhole. The wormholes may be output in any order, and the endpoints $u_m, v_m$ of each wormhole may be in any order.
[Note]
Be sure to flush standard output after each output (query and answer). If you do not flush, you may get TLE or WA.
Print a newline at the end.
Constraints
- $2 \le N \le 400$
- $N$ is an integer
- The total number of hidden wormholes $M$ satisfies $0 \le M \le 400$
- There are no wormholes connecting a station to itself, and no multiple wormholes connecting the same pair of stations
- The maximum number of queries you can send is $4,500$
Sample
Sample 1
Input
4 1 0 1 1
Output
? 1 3 1 2 3 4 ? 1 1 1 3 ? 1 1 1 2 ? 2 2 1 2 3 4 ! 2 1 2 2 4
This sample shows an example of the interaction when $N=4$ and there are $2$ hidden wormholes, connecting stations $1$ and $2$, and stations $2$ and $4$. (Note: in an actual run, input and output take place interactively.)
- Send
? 1 3 1 2 3 4($A=\{1\}, B=\{2,3,4\}$). Since there is a wormhole connecting stations $1$ and $2$, $1$ is returned. - Send
? 1 1 1 3($A=\{1\}, B=\{3\}$). Since no wormhole exists, $0$ is returned. - Send
? 1 1 1 2($A=\{1\}, B=\{2\}$). Since a wormhole exists, $1$ is returned. - Send
? 2 2 1 2 3 4($A=\{1,2\}, B=\{3,4\}$). Since there is a wormhole connecting stations $2$ and $4$, $1$ is returned.
Sample 2
Input
3 0
Output
? 1 2 1 2 3 ! 0
Sample 3
Input
3 1 1 1 1
Output
? 1 2 1 2 3 ? 1 1 1 2 ? 1 1 1 3 ? 1 1 2 3 ! 3 1 2 1 3 2 3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。