这是一个交互问题。
Alice 有一个树 $$$T$$$,由 $$$n$$$ 个节点组成,编号从 $$$1$$$ 到 $$$n$$$。 Alice 将向 Bob 显示 $$$T$$$。观察 $$$T$$$ 后,Bob 需要告诉 Alice $$$[1, 2, \ldots, n]$$$ 的两个排列 $$$p_1$$$ 和 $$$p_2$$$。
然后,Alice 将玩以下游戏 $$$q$$$ 轮。
- Alice 将创建一个数组 $$$a$$$,它是 $$$[0,1,\ldots,n-1]$$$ 的排列。节点 $$$v$$$ 的值将为 $$$a_v$$$。
- Alice 将选择 $$$T$$$ 的两个节点 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$) 并将它们告诉 Bob。 Bob 需要找到节点 $$$u$$$ 和 $$$v$$$ 之间唯一简单路径上的值的 $$$\operatorname{MEX}^\dagger$$$ 值。
- 为了找到这个值,Bob 最多可以向 Alice 询问 $$$5$$$ 查询。在每个查询中,Bob 应向 Alice 提供三个整数 $$$t$$$、$$$l$$$ 和 $$$r$$$,使得 $$$t$$$ 为 $$$1$$$ 或 $$$2$$$,并且 $$$1 \leq l \leq r \leq n$$$。然后,爱丽丝将告诉鲍勃,该值等于 $$$$$$\min_{i=l}^{r} a[p_{t,i}].$$$$$$
请注意,所有回合都是相互独立的。特别地,$$$a$$$、$$$u$$$和$$$v$$$的值在不同轮次中可以不同。
Bob 很困惑,因为他只知道 HLD 解决方案,每轮需要 $$$O(\log(n))$$$ 查询。所以他需要你的帮助来赢得比赛。
$$$^\dagger$$$ 整数集合 $$$c_1, c_2, \ldots, c_k$$$ 的 $$$\operatorname{MEX}$$$ (最小排除)被定义为集合 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。
互动
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。阅读它。测试用例的描述如下。
每个测试用例的第一行包含两个正整数 $$$n$$$ 和 $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq q \leq 10^4$$$) - 分别是 $$$T$$$ 中的节点数和轮数。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$) - 表示节点 $$$u$$$ 和 $$$v$$$ 之间的边。保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 和 $$$q$$$ 之和分别不超过 $$$10^5$$$ 和 $$$10^4$$$。
还保证$$$n \cdot q$$$ 之和不超过$$$3 \cdot 10^6$$$。
每个测试用例的交互首先输出 $$$[1, 2, \ldots, n]$$$ 的两个排列 $$$p_1$$$ 和 $$$p_2$$$。
在新行中,输出 $$$n$$$ 以空格分隔的不同整数,表示 $$$p_1$$$。
在下一行中,输出 $$$n$$$ 以空格分隔的不同整数,表示 $$$p_2$$$。
Alice 将开始玩游戏。
对于每一轮,您必须读取两个整数,$$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$)。您需要找到节点 $$$u$$$ 和 $$$v$$$ 之间唯一简单路径上的值的 $$$\operatorname{MEX}$$$。
要进行查询,请输出不带引号的“? $$$t$$$ $$$l$$$ $$$r$$$”,这样 $$$t$$$ 可以是 $$$1$$$ 或 $$$2$$$,并且 $$$1 \leq l \leq r \leq n$$$。之后,您应该读取一个整数 - 您的查询 $$$\min_{i=l}^{r} a_{p_{t,i}}$$$ 的答案。每轮最多可以进行 $$$5$$$ 这样的查询。
如果要打印答案,请输出“! $$$x$$$” ($$$1 \leq x, y \leq n$$$),不带引号。完成此操作后,读取一个整数,该整数通常等于 $$$1$$$。
如果您收到整数 $$$-1$$$ 而不是有效回复,则意味着您的程序进行了无效查询,超出了查询限制,或者对上一个测试用例给出了错误答案。您的程序必须立即终止才能收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
打印查询或答案后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解,请遵循以下测试格式。
第一行应包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行应包含两个正整数 $$$n$$$ 和 $$$q$$$ ($$$2 \leq n \leq 10^5$$$; $$$1 \leq q \leq 10^4$$$) - 分别是 $$$T$$$ 中的节点数和轮数。
接下来的 $$$n-1$$$ 行应包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$) - 表示节点 $$$u$$$ 和 $$$v$$$ 之间的边。给定的边必须形成一棵树。
对于每轮 $$$q$$$,首先在新行上打印 $$$[0, 1, 2, \ldots, n-1]$$$ 的排列,表示 Alice 在该轮开始时选择的数组 $$$a$$$。
在下面的行中,打印两个不同的节点 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq v$$$, $$$u \neq v$$$),代表 Alice 所询问路径的端点。
所有测试用例的 $$$n$$$ 和 $$$q$$$ 总和不应分别超过 $$$10^5$$$ 和 $$$10^4$$$。
$$$n \cdot q$$$ 的总和不应超过 $$$3 \cdot 10^6$$$。
示例
输入 #1
1 3 1 1 2 2 3 2 3 1 0 1
输出 #1
1 2 3 2 1 3 ? 1 2 3 ? 2 1 3 ! 0
注意
在第一个测试中,交互进行如下。
SolutionJuryExplanation1有1个测试用例。3 1树$$$T$$$由$$$3$$$节点组成,Alice只玩一轮。1 2$$$T$$$的第一条边2 3$$$T$$$的第二条边1 2 3排列$$$p_1$$$2 1 3排列$$$p_2$$$Alice 将 $$$a$$$ 洗牌为 $$$a=[0,2,1]$$$,然后给出唯一一轮的节点。2 3 该轮的节点? 1 2 31$$$\min(a_{p_{1,2}},a_{p_{1,3}})=\min(a_2,a_3)=1$$$? 2 1 30$$$\min(a_{p_{2,1}},a_{p_{2,2}},a_{p_{2,3}})=\min(a_2,a_1,a_3)=0$$$! 01考虑查询的输出,很明显$$$\operatorname{MEX}$$$ 是$$$0$$$。由于输出是正确的,陪审团以 $$$1$$$ 回应。
在每个测试用例之后,请确保阅读 $$$1$$$ 或 $$$-1$$$。