G. NPC Challenge
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a hidden undirected tree consisting of $$$n$$$ vertices. To find this tree, you may ask queries of the following form:

  • Pick a sequence of distinct vertices $$$a_1, a_2, \ldots, a_k$$$, where $$$k \ge 1$$$.

The interactor will process your sequence and return a subset of these vertices, denoted by $$$S$$$. The set $$$S$$$ is generated by the following process:

  • Initially, $$$S$$$ is an empty set.

  • The interactor processes the vertices in the exact order they appear in your sequence, from $$$a_1$$$ to $$$a_k$$$.

  • For each $$$a_i$$$, if $$$a_i$$$ does not share an edge with any vertex that is currently in $$$S$$$, then $$$a_i$$$ is added to $$$S$$$. Otherwise, $$$a_i$$$ is ignored.

  • After processing all $$$k$$$ vertices, the interactor returns the final set $$$S$$$ to you. $$$S$$$ is represented by a binary string $$$s$$$ of length $$$k$$$, where $$$s_i=\texttt{1}$$$ if and only if $$$a_i \in S$$$.

Your task is to find all $$$n-1$$$ edges of the hidden tree. To make the problem harder, the sum of $$$k$$$ over all queries must not exceed $$$30 \cdot n$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 10^3$$$), representing the number of vertices in the hidden tree.

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

Interaction

To make a query, output a line in the following format:

  • $$$\mathtt{?}\;k\;a_1\;a_2\;\ldots\;a_k$$$ ($$$1 \le k \le n$$$, $$$1 \le a_i \le n$$$, $$$a_i \ne a_j$$$ for all $$$1 \le i \lt j \le k$$$)

As a response to the query, you will receive a binary string of length $$$k$$$, representing $$$S$$$.

To report the answer, first output $$$\mathtt{!}$$$ on a single line. Then, output $$$n-1$$$ lines, where the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$, representing an undirected edge between vertices $$$u_i$$$ and $$$v_i$$$. You may output the edges in any order.

After this, proceed to the next test case or terminate if this is the last test case.

The interactor is not adaptive. This means that the hidden tree is fixed before any queries are made and will not change throughout the interaction.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks

To hack, use the following format.

The first line shoud contain a single integer $$$t$$$ ($$$1 \le t \le 100$$$), representing the number of test cases.

The first line of each test case should contain an integer $$$n$$$ ($$$2 \le n \le 10^3$$$), representing the number of vertices in the tree.

Each of the next $$$n-1$$$ lines should contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), representing an edge in the tree. You need to guarantee that the edges form a valid tree.

The sum of $$$n$$$ over all test cases should not exceed $$$10^3$$$.

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
2
2

10


5

101

10101
Output


? 2 1 2

!
2 1

? 3 1 2 5

? 5 5 3 4 2 1

!
3 5
1 2
3 2
2 4
Note

In the first test case, the hidden tree consists of $$$n=2$$$ vertices, and the only edge is $$$(1,2)$$$.

  • For the first query, $$$a=[1,2]$$$:

    • Vertex $$$1$$$ is processed. Currently, $$$S$$$ is empty. Since $$$1$$$ has no neighbors in $$$S$$$, it is added to $$$S$$$. $$$S$$$ becomes $$$\{1\}$$$.

    • Vertex $$$2$$$ is processed. Its neighbor, vertex $$$1$$$, is already in $$$S$$$. Thus, vertex $$$2$$$ is ignored.

In the second test case, the hidden tree consists of $$$n=5$$$ vertices. The edges are $$$(1, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, and $$$(3, 5)$$$.

  • For the first query, $$$a=[1,2,5]$$$:

    • Vertex $$$1$$$ is processed. $$$S$$$ is empty. It is added to $$$S$$$. $$$S$$$ becomes $$$\{1\}$$$.

    • Vertex $$$2$$$ is processed. It shares an edge with vertex $$$1 \in S$$$. It is ignored.

    • Vertex $$$5$$$ is processed. Its only neighbor is vertex $$$3 \notin S$$$. It is added to $$$S$$$. $$$S$$$ becomes $$$\{1, 5\}$$$.

  • For the second query, $$$a=[5,3,4,2,1]$$$:

    • Vertex $$$5$$$ is processed. $$$S$$$ is empty. It is added to $$$S$$$. $$$S$$$ becomes $$$\{5\}$$$.

    • Vertex $$$3$$$ is processed. It shares an edge with vertex $$$5 \in S$$$. It is ignored.

    • Vertex $$$4$$$ is processed. Its only neighbor is vertex $$$2 \notin S$$$. It is added to $$$S$$$. $$$S$$$ becomes $$$\{4, 5\}$$$.

    • Vertex $$$2$$$ is processed. It shares an edge with vertex $$$4 \in S$$$. It is ignored.

    • Vertex $$$1$$$ is processed. Its only neighbor is vertex $$$2 \notin S$$$. Since it has no neighbors in $$$S$$$, it is added to $$$S$$$.