Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
E. My Mind Is Going
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

Out of boredom, you decided to pass the time by playing a game of your own invention with the onboard supercomputer. The game works as follows: the supercomputer shows you a bipartite graph $$$G$$$ on $$$n$$$ vertices, and then chooses a secret pair of distinct edges $$$e_1$$$ and $$$e_2$$$ that are absent from it and have the following properties:

  • the graph $$$G \cup \{e_1\}$$$ is bipartite;
  • the graph $$$G \cup \{e_2\}$$$ is bipartite;
  • the graph $$$G' = G \cup \{e_1, e_2\}$$$ is not bipartite.

Your task is to guess at least one of the secret edges. To do this, you may use two types of queries:

  • ? 1 $$$k \; v_1 \; v_2 \; \ldots \; v_k$$$ ($$$1 \le k \le n$$$, all $$$v_i$$$ are distinct): choose a set of $$$k$$$ vertices and find out whether the subgraph of $$$G'$$$, consisting only of these vertices and the edges of $$$G'$$$ connecting them, is bipartite;
  • ? 2 $$$u \; v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$): find out whether $$$G'$$$ contains the edge $$$(u, v)$$$.

It is guaranteed that graph $$$G$$$ is such that the supercomputer can choose a pair of edges with the properties described above.

Since the manufacturer of supercomputers of your model has introduced new quotas on RAM usage, you may make no more than $$$33$$$ queries.

Note that the interactor is non-adaptive: the hidden edges $$$e_1$$$ and $$$e_2$$$ are fixed before the interaction begins and do not depend on your queries.

Input

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

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$4 \le n \le 2000$$$, $$$1 \le m \le \min\left(2 \cdot 10^5, \dfrac{n(n-1)}{2}\right)$$$) — the number of vertices and edges in graph $$$G$$$.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) — an edge of graph $$$G$$$.

It is guaranteed that graph $$$G$$$ is bipartite, contains no multiple edges, and that there exists a pair of edges $$$e_1$$$ and $$$e_2$$$ with the properties described above.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$4 \cdot 10^6$$$.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Interaction

For each test case, first read graph $$$G$$$ in the format described above, after which you may make no more than $$$33$$$ queries of two types:

  • ? 1 $$$k \; v_1 \; v_2 \; \ldots \; v_k$$$ ($$$1 \le k \le n$$$, all $$$v_i$$$ are distinct). In response, you will receive 1 if the subgraph of $$$G'$$$, consisting only of the specified vertices and the edges of $$$G'$$$ connecting them, is bipartite, and 0 otherwise.
  • ? 2 $$$u \; v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$). In response, you will receive 1 if the edge $$$(u, v)$$$ is present in graph $$$G'$$$, and 0 otherwise.

To report your answer, output one of the hidden edges in the format ! $$$u \; v$$$. After that, immediately proceed to the next test case. Outputting the answer does not count as a query.

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.

Hack format

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$, the next $$$m$$$ lines contain the edges of graph $$$G$$$ in the format described above. Each of the next two lines contains two integers $$$u$$$ and $$$v$$$ — the edges $$$e_1$$$ and $$$e_2$$$. Graph $$$G$$$ and edges $$$e_1$$$, $$$e_2$$$ must satisfy all the constraints and properties described above.

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

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Interaction log
< 2
< 4 2
< 1 2
< 3 4
> ? 1 3 1 3 4
< 0
> ? 2 1 3
< 1
> ! 1 3
< 5 3
< 1 2
< 2 3
< 4 5
> ? 2 1 4
< 1
> ! 1 4
Note

In the first test case, the hidden edges are $$$(1, 3)$$$ and $$$(1, 4)$$$. The first query selects vertices $$$1$$$, $$$3$$$, and $$$4$$$, which form a triangle in $$$G'$$$, so the response is $$$0$$$. The second query confirms that edge $$$(1, 3)$$$ exists, and we report this hidden edge.

In the second test case, the hidden edges are $$$(1, 4)$$$ and $$$(3, 5)$$$. The query confirms that edge $$$(1, 4)$$$ exists, and we report this hidden edge.