有一个带 $$$n$$$ 节点和 $$$n-1$$$ 边的加权树。节点被方便地标记为从 $$$1$$$ 到 $$$n$$$。权重最多为 $$$100$$$ 正整数。将两个节点之间的距离定义为节点之间唯一路径上的边之和。您想找到树的直径。直径是一对节点之间的最大距离。
不幸的是,这棵树没有给你,但你可以问一些关于它的问题。在一个问题中,您可以指定两个非空不相交的节点集 $$$p$$$ 和 $$$q$$$,判断器将返回 $$$p$$$ 中的节点与 $$$q$$$ 中的节点之间的最大距离。换句话说,$$$x$$$ 和 $$$y$$$ 之间的最大距离,其中 $$$x \in p$$$ 和 $$$y \in q$$$。在询问不超过 $$$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} dist(a_p, b_q)$$$。如果您得到 $$$-1$$$ 的结果(因为您打印了无效的查询),请立即退出以避免得到其他结论。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
当您准备好回答时,请打印“$$$-1\ d$$$”,其中 $$$d$$$ 是所有节点对上的最大最短距离。
每个测试用例最多只能提出 $$$9$$$ 问题。
黑客格式
要破解,请使用以下格式。请注意,您只能使用一个测试用例进行破解。
第一行应包含单个整数 $$$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$$$。这些边必须形成一棵树。
示例
输入 #1
2 5 9 6 10 9 10 2 99
输出 #1
1 4 1 2 3 4 5 1 4 2 3 4 5 1 1 4 3 4 5 1 2 1 4 4 5 1 2 3 1 4 5 1 2 3 4 -1 10 1 1 1 2 -1 99
注意
在第一个示例中,第一棵树如下所示:
在第一个问题中,我们有 $$$p = {1}$$$,$$$q = {2, 3, 4, 5}$$$。 $$$p$$$ 中的节点与 $$$q$$$ 中的节点之间的最大距离为 $$$9$$$(节点 $$$1$$$ 和 $$$5$$$ 之间的距离)。
第二棵树有两个节点,节点之间有一条边,权重为 $$$99$$$。