这是一个交互问题.
在这个交互式问题中,给定一个由 $$$n$$$ 个顶点组成的非循环、连通、无向图。我们将两个顶点 $$$v$$$ 和 $$$u$$$ 之间的路径定义为以下序列 不同 上面写着 顶点 $$$p_1, p_2,\dots p_k$$$ 使得 $$$p_1 = v$$$, $$$p_k = u$$$, 并且对于所有 $$$i$$$ ($$$1 \le i \lt k$$$), 顶点 $$$p_i$$$ 和$$$p_{i+1}$$$。
有隐藏顶点 $$$x$$$ 和 $$$y$$$ (它们可能重合)。您可以进行以下查询:
- 选择两个顶点 $$$a$$$, $$$b$$$ ($$$1\le a, b\le n$$$)。如果顶点 $$$x$$$、$$$y$$$ 之间的路径与顶点 $$$a$$$、$$$b$$$ 之间的路径共享至少一个公共顶点,则评审团将响应 $$$1$$$,否则将响应 $$$0$$$。
请注意,交互器是 自适应,这意味着隐藏的顶点可能会根据您的查询而变化,但不会与之前的查询相矛盾。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。以下几行描述了测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 图中的顶点数。
接下来有 $$$n - 1$$$ 行,每行包含两个整数 $$$v$$$、$$$u$$$ ($$$1\le v, u\le n$$$),表示顶点 $$$v$$$ 和 $$$u$$$ 通过图中的边连接。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
互动
要查找路径上的任何顶点,您最多可以使用 $$$\lfloor\frac{n}{2}\rfloor + 1$$$ 查询。为此,请使用“? $$$a$$$ $$$b$$$”形式的查询。
每次查询后,读取一个数字,$$$0$$$ 或 $$$1$$$ — 对查询的响应。
当找到所需顶点之一时,按以下格式输出一行:“! $$$v$$$” ($$$1\le v\le n$$$),其中 $$$v$$$ 是您找到的顶点。
如果您的程序对一个测试用例进行了超过 $$$\lfloor\frac{n}{2}\rfloor + 1$$$ 查询,则 对查询的答复将 为 $$$-1$$$,收到这样的响应后,您的程序应立即终止以接收以下判决 错误答案。否则,它可能会收到任何其他判决。
输出查询后,不要忘记输出换行符并刷新输出缓冲区。否则,您将收到以下判决: 解决方案“超时”。要刷新缓冲区,请使用:
- $$$\tt{fflush(stdout)}$$$ 或 $$$\tt{cout.flush()}$$$ 在 C++ 中;
- $$$\tt{System.out.flush()}$$$ 在 Java 中;
- $$$\tt{flush(输出)}$$$(帕斯卡);
- $$$\tt{stdout.flush()}$$$ 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
3 2 1 2 1 3 1 2 1 3 0 0 4 1 2 2 3 2 4 0 1
输出复制
? 1 1 ! 1 ? 1 1 ? 2 2 ! 3 ? 1 3 ? 4 4 ! 4