题目描述

这是一个交互题。

在本题中，给定一个无环、连通、无向图，共有 $n$ 个顶点。我们定义两个顶点 $v$ 和 $u$ 之间的路径为一系列不重复的顶点 $p_1, p_2, \dots, p_k$，使得 $p_1 = v$，$p_k = u$，且对于所有 $i$（$1 \le i < k$），都存在一条边连接顶点 $p_i$ 和 $p_{i+1}$。

有两个隐藏的顶点 $x$ 和 $y$（它们可能相同）。你可以进行如下操作：

• 选择两个顶点 $a$ 和 $b$（$1 \le a, b \le n$），系统会回答：如果从 $x$ 到 $y$ 的路径与从 $a$ 到 $b$ 的路径有至少一个公共顶点，那么返回 $1$，否则返回 $0$。

你的任务是在不超过 $\lfloor\frac{n}{2}\rfloor + 1$ 次询问内，找出 $x$ 到 $y$ 路径上的至少一个顶点。注意，交互器是自适应的，也就是说，隐藏顶点 $x$ 和 $y$ 可能会依据你的询问发生改变，但不会与先前的回答矛盾。

输入格式

每组测试包含多组数据。第一行包含一个整数 $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$。

输出格式

样例

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

样例说明

由 ChatGPT 5 翻译

来源

Codeforces 2193G，英文题名 Paths in a Tree。