← 返回题目列表

Codeforces · 2164/G

G. 毫无意义的机器

中文机器翻译题面 查看原题

这是一个交互问题。

玛德琳正在玩一台毫无意义的机器。无意义的机器有一棵隐藏的树,大小为$$$n$$$,玛德琳必须通过询问机器来找到树的边缘。

在查询中,Madeline 会给机器一个 $$$p$$$ 的排列 $$$[1,2,\ldots,n]$$$,机器将返回一个序列 $$$q_1, q_2, \ldots, q_n$$$,其中 $$$q_i$$$ 是由顶点形成的导出子图的边数$$$\{p_1,p_2,\ldots,p_i\}$$$。

这里,由顶点子集 $$$V' \subseteq V$$$ 形成的图 $$$G(V,E)$$$ 的导出子图是由该子集中的顶点以及原始图 $$$G$$$ 中存在的子集的顶点之间的所有边组成的图。

不过,机器运行速度很慢,所以Madeline只能在所有查询完成后才能立即得到结果。这台机器的内存也不是很大,所以梅德琳只能问$$$31$$$次。她不知道如何解决,所以她邀请你来帮助她。

请注意,交互器是 非自适应。也就是说,树是预先固定的,不会随着您的查询而改变。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$3\le n\le 5\cdot 10^4$$$) — 树的大小。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^4$$$。

互动

交互从读取整数 $$$n$$$ 开始。

然后,输出单个整数 $$$k$$$ ($$$1 \leq k \leq 31$$$) — 查询数。

要提出查询,请按以下格式输出一行:

  • $$$p_{i,1}\,p_{i,2}\,\ldots\,p_{i,n}$$$ ($$$1 \leq p_{i,j} \leq n$$$, $$$p_{i,j}$$$ 对于每个 $$$i$$$ 都是不同的) — 如上所述的查询。

一旦您询问完所有 $$$k$$$ 查询,请读取 $$$k$$$ 行 $$$n$$$ 整数 $$$q_{i,j}$$$ — 对上述查询的响应。

当你知道隐藏树时,按以下格式输出 $$$n-1$$$ 行:

  • $$$u,v$$$ ($$$1\leq u,v\leq n$$$) — 隐藏树中的边 $$$(u,v)$$$。

然后,继续进行下一个测试用例,或者如果没有更多的测试用例则终止程序。

打印所有 $$$k$$$ 查询后,不要忘记输出行尾并刷新 $$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

黑客

要破解,请使用以下格式。

第一行应包含单个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。

每个测试用例的第二行应包含一个整数 $$$n$$$ ($$$3 \le n \le 5\cdot 10^4$$$)。

接下来的 $$$n - 1$$$ 行中的第 $$$i$$$ 行应包含两个整数 $$$u_i, v_i$$$ ($$$1 \le u_i, v_i \le n$$$)。

给定的边应该形成一棵树,并且所有测试用例的 $$$n$$$ 总和不应超过 $$$5 \cdot 10^4$$$。

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中; Java 中的
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

3
3



0 1 2
0 0 2


4




0 1 1 3
0 1 1 3
0 1 2 3



5


0 0 1 3 4




输出
复制


2
1 2 3
1 3 2


1 2
2 3

3
3 2 4 1
1 4 3 2
1 2 3 4



2 3
1 2
4 1

1
1 2 3 4 5

1 4
4 3
3 2
5 3

注意

展示台链接

对于第一个测试用例:

  • 第一个查询有答案 0 1 2,因为只有边 $$$(1, 2)$$$ 位于 $$$\{1,2\}$$$ 形成的导出子图中。
  • 第二个查询有答案 0 0 2,因为 $$$\{1,3\}$$$ 形成的导出子图中没有边。

对于第三个测试用例:

  • 边 $$$(2,3)$$$、$$$(3,4)$$$ 和 $$$(4,1)$$$ 位于 $$$\{1,2,3,4\}$$$ 形成的导出子图中,因此 $$$q_{1,4}=3$$$。