这是一个交互问题。
给你一棵树——无环的连通无向图。树的一个顶点是特殊的,你必须找到哪一个。你可以按照以下形式提出问题:给定树的一条边,哪个端点距离特殊顶点更近,意味着哪个端点到特殊顶点的最短路径包含更少的边。对于给定的树,您必须通过在最坏情况下询问最少数量的问题来找到特殊顶点。
请注意,交互器可能不会提前固定特殊顶点:它可能会将顶点更改为任何其他顶点,但要求与之前给出的答案一致。
输入
给你一个整数 $$$n$$$ ($$$2 \le n \le 100$$$) — 树中的顶点数。
下面的 $$$n-1$$$ 行每行包含两个整数,$$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$),表示树中连接 $$$u$$$ 和 $$$v$$$ 的边。保证给定的边形成一棵树。
互动
读取输入数据后,就可以开始查询了。有两种可能的查询:
1. "?$$$u$$$ $$$v$$$" — 询问一条边 $$$(u, v)$$$ ($$$1 \le u, v \le n$$$) 哪个端点更接近特殊顶点。该查询的答案是端点之一。请注意,$$$u$$$ 和 $$$v$$$ 必须通过边连接,因此它们到特殊顶点的距离不能相同。
2.“!$$$u$$$”— 表示您找到了特殊顶点。程序完成此操作后,必须立即终止。
不要忘记输出行尾并刷新输出。否则您将得到超出空闲限制的判决。要刷新输出,您可以使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 sys.stdout.flush() ;
- 请参阅其他语言的文档。
如果您询问的查询数量超过了给定树在最坏情况下所需的数量,您将得到错误的答案。
示例
输入 #1
5 1 2 2 3 3 4 4 5 3 2 1
输出 #1
? 3 4 ? 2 3 ? 1 2 ! 1
输入 #2
5 2 1 3 1 4 1 5 1 1 1 4
输出 #2
? 1 2 ? 1 3 ? 1 4 ! 4
注意
此任务禁止黑客攻击。