这是一个交互问题。
玛德琳正在玩一台毫无意义的机器。无意义的机器有一棵隐藏的树,大小为$$$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$$$。