这是一个交互问题。
存在一棵由 $$$n$$$ 个节点组成的未知树,该树只有一个质心。一开始你只知道$$$n$$$,你的任务是找到树的质心。
您最多可以询问任意两个顶点之间的距离 $$$2\cdot10^5$$$ 次。
请注意,交互器不具有自适应性。也就是说,树在每次测试中都是预先固定的,不依赖于您的查询。
如果一个顶点的移除将树分割成每个最多包含 $$$\lfloor\frac{n}{2}\rfloor$$$ 个顶点的子树,则该顶点称为质心。
输入
输入的唯一行包含一个整数 $$$n$$$ ($$$3\le n\le 7.5\cdot10^4$$$) — 树中的节点数。
互动
通过阅读 $$$n$$$ 开始交互。
要查询两个节点 $$$u, v$$$ ($$$1 \le u, v \le n$$$) 之间的距离,请输出“? u v”。
如果确定树的质心为$$$x$$$,则使用“!x”报告。
打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
在此问题中,黑客被禁用。
保证此问题最多有 $$$500$$$ 测试。
示例
输入 #1
5 2 1 2 3 1 1 1
输出 #1
? 1 2 ? 1 3 ? 1 4 ? 1 5 ? 2 3 ? 3 4 ? 4 5 ! 3
注意
这是示例中的树图像。