CF1444E Finding the Vertex

这是一个交互题。 给定一棵树——即一个无环连通无向图。其中有一个特殊的顶点，你需要找出它是哪一个。你可以进行如下形式的提问：给定树上的一条边，询问哪一个端点距离特殊顶点更近，也就是说，哪一个端点到特殊顶点的最短路径包含的边数更少。你需要通过最少次数的提问，在最坏情况下找出特殊顶点。 请注意，特殊顶点可能不是事先固定的：交互器可以在保证之前所有回答一致的前提下，随时将特殊顶点更换为其他顶点。

输入一个整数 $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` —— 表示你已经找到特殊顶点 $u$。在输出该操作后，程序必须立即终止。 不要忘记在每次输出后换行并刷新输出缓冲区，否则会收到“Idleness limit exceeded”的判定。刷新输出的方法如下： - C++：`fflush(stdout)` 或 `cout.flush()`； - Java：`System.out.flush()`； - Pascal：`flush(output)`； - Python：`sys.stdout.flush()`； - 其他语言请查阅相关文档。 如果你在某棵树上询问次数超过了最坏情况下所需的最小次数，将会收到 Wrong answer 的判定。

本题禁止 Hack。 由 ChatGPT 4.1 翻译