E1. Interactive Graph (Simple Version)

时间限制：每个测试点2秒
内存限制：每个测试点256兆字节

问题描述

这是本题的简单版本。两个版本的区别在于：在本版本中，你可以询问不超过 $32 \cdot (n + m)$ 次问题，且 $n \le 15$ 。只有当你解决了本题的所有版本时，才可以进行攻击（Hack）。

这是一个交互式问题。

评测系统构想了一个无环、无重边的有向图，该图有 $n$ 个顶点和 $m$ 条边。

你的任务是确定这个图中有哪些边。为此，你可以提出如下形式的问题：在图的所有路径的字典序* 排序列表中，第 $k$ 条路径是什么？

图中的一条路径是一个顶点序列 $u_1, u_2, \ldots, u_l$ ，使得对于任意 $i < l$ ，图中存在边 $(u_i, u_{i+1})$ 。

你的目标是在不超过 $32 \cdot (n + m)$ 次询问内完成此任务。

每个测试包含多个测试用例。第一行包含一个整数 $t$ ，表示测试用例的数量（ $1 \le t \le 10$ ）。
接下来是每个测试用例的描述。

每个测试用例由单独一行组成，包含一个整数 $n$ （ $1 \le n \le 15$ ）——图中顶点的数量。

评测系统保证给定的图不包含环或重边。

注意： $m$ 对你来说是未知的。

对于每个测试用例，交互过程从读取整数 $n$ 开始。

之后你可以提出最多 $32 \cdot (n + m)$ 次询问。

询问方式：输出格式为 "? k"（不含引号），其中 $1 \le k \le 2^{30}$ 。
每次询问后，你需要读取一个整数 $q$ —— 第 $k$ 条路径的顶点数。
- 如果 $q = 0$ ，则表示该路径不存在；
- 否则，再读取 $q$ 个整数，表示构成这条路径的顶点编号。

可以证明，在给定约束下，图中不同的路径总数不超过 $2^{30}$ 。

回答答案：首先输出格式为 "! m" 的字符串，然后输出 $m$ 行，每行格式为 "u v"，表示存在一条从 $u$ 到 $v$ 的有向边。你可以按任意顺序输出这些边。输出答案不计入询问次数。

每次询问后，不要忘记输出换行并刷新缓冲区。否则，你将收到“Idleness limit exceeded”的判决。

如果在任何交互步骤中，你读取到 $-1$ 而非有效数据，你的解决方案必须立即退出。这意味着你的解决方案将因无效查询或其他错误而被判“Wrong answer”。未能及时退出可能导致任意判决，因为你的解决方案将继续从已关闭的流中读取数据。

攻击（Hack）格式：

对于攻击，请使用以下格式：

第一行包含一个整数 $t$ （ $1 \le t \le 10$ ）——测试用例数量。

每个测试用例的第一行包含两个整数 $n, m$ （ $1 \le n \le 15$ ， $0 \le m \le \frac{n \cdot (n-1)}{2}$ ）——顶点数和边数。

接下来的 $m$ 行包含边的描述。每条边由两个整数 $v, u$ （ $1 \le v, u \le n$ ， $v \ne u$ ）定义，表示从 $v$ 到 $u$ 的一条有向边。

该图不能包含环或重边。

输入示例：

输出示例：

（本交互示例展示了三个测试用例的完整交互过程，具体图结构请参考原题。）

Note

The graph for the first test case.

In this graph, there are $15$ paths, which are arranged in lexicographic order as follows: