CF1146C.Tree Diameter

There is a weighted tree with $n$ nodes and $n-1$ edges. The nodes are conveniently labeled from $1$ to $n$. The weights are positive integers at most $100$. Define the distance between two nodes to be the sum of edges on the unique path between the nodes. You would like to find the diameter of the tree. Diameter is the maximum distance between a pair of nodes.

Unfortunately, the tree isn't given to you, but you can ask some questions about it. In one question, you can specify two nonempty disjoint sets of nodes $p$ and $q$, and the judge will return the maximum distance between a node in $p$ and a node in $q$. In the words, maximum distance between $x$ and $y$, where $x \in p$ and $y \in q$. After asking not more than $9$ questions, you must report the maximum distance between any pair of nodes.

Interaction

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

The first line of each test case contains an integer $n$ ($2 \leq n \leq 100$) — the number of nodes in the tree.

To ask a question, print "$k_1\ k_2\ a_1\ a_2\ \ldots\ a_{k_1}\ b_1\ b_2\ \ldots\ b_{k_2}$" $(k_1, k_2 \geq 1$ and $k_1+k_2 \leq n$). These two sets must be nonempty and disjoint. The judge will respond with a single integer $\max_{p,q} dist(a_p, b_q)$. If you ever get a result of $-1$ (because you printed an invalid query), exit immediately to avoid getting other verdicts.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

When you are ready to answer, print "$-1\ d$", where $d$ is the maximum shortest distance over all pairs of nodes.

You can only ask at most $9$ questions per test case.

Hack Format

To hack, use the following format. Note that you can only hack with one test case.

The first line should contain a single integer $t$ ($t=1$).

The second line should contain a single integer $n$ ($2 \leq n \leq 100$).

Each of the next $n-1$ lines should contain three integers $a_i, b_i, c_i$ ($1\leq a_i, b_i\leq n$, $1 \leq c_i \leq 100$). This denotes an undirected edge between nodes $a_i$ and $b_i$ with weight $c_i$. These edges must form a tree.

有一棵带权树，包含 $n$ 个节点和 $n-1$ 条边。节点被方便地标号为 $1$ 到 $n$。边权为不超过 $100$ 的正整数。定义两个节点之间的距离为连接这两个节点的唯一路径上所有边的权值之和。你需要求出该树的直径，即所有节点对之间距离的最大值。

不幸的是，这棵树并未直接给出，但你可以向交互系统提出若干问题来获取信息。每次提问时，你可以指定两个非空且互不相交的节点集合 $p$ 和 $q$，评测机会返回一个节点 $x \in p$ 与一个节点 $y \in q$ 之间的最大距离（即 $\max_{x \in p,\, y \in q} \mathrm{dist}(x, y)$）。在至多 $9$ 次提问之后，你必须报告所有节点对之间的最大距离。

交互方式

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 1\,000$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 100$），表示树中节点的数量。

要提出一个问题，请输出格式为：
$k_1\ k_2\ a_1\ a_2\ \ldots\ a_{k_1}\ b_1\ b_2\ \ldots\ b_{k_2}$
其中 $k_1, k_2 \geq 1$ 且 $k_1 + k_2 \leq n$。这两个集合必须非空且互不相交。评测机将返回一个整数：$\max_{p,q} \mathrm{dist}(a_p, b_q)$。若你输出了非法查询并得到结果 $-1$，请立即退出程序，以免收到其他错误提示。

每次输出查询后，务必输出换行符并刷新输出缓冲区；否则你会收到“Idleness limit exceeded”（空闲超时）判据。为此，请使用以下方式：

• C++ 中使用 fflush(stdout) 或 cout.flush()；
• Java 中使用 System.out.flush()；
• Pascal 中使用 flush(output)；
• Python 中使用 stdout.flush()；
• 其他语言请参考相应文档。

当你准备好回答时，请输出 -1 d，其中 $d$ 是所有节点对之间的最大距离。

每个测试用例最多只能提出 $9$ 次询问。

Hack 格式

用于 Hack 的输入格式如下（注意：你只能对单个测试用例进行 Hack）：

第一行应为一个整数 $t$（$t = 1$）。

第二行应为一个整数 $n$（$2 \leq n \leq 100$）。

接下来的 $n-1$ 行，每行包含三个整数 $a_i, b_i, c_i$（$1 \leq a_i, b_i \leq n$，$1 \leq c_i \leq 100$），表示节点 $a_i$ 与 $b_i$ 之间存在一条权重为 $c_i$ 的无向边。这些边必须构成一棵树。

In the first example, the first tree looks as follows:

In the first question, we have $p = {1}$, and $q = {2, 3, 4, 5}$. The maximum distance between a node in $p$ and a node in $q$ is $9$ (the distance between nodes $1$ and $5$).

The second tree is a tree with two nodes with an edge with weight $99$ between them.

在第一个例子中，第一棵树如下所示：

在第一个问题中，我们有 $p = \{1\}$，且 $q = \{2, 3, 4, 5\}$。$p$ 中节点与 $q$ 中节点之间的最大距离为 $9$（即节点 $1$ 与节点 $5$ 之间的距离）。

第二棵树是一棵仅含两个节点的树，两节点之间有一条权值为 $99$ 的边。