题目描述

$\textbf{这是一道交互题。}$

给定一棵有 $n$ 个节点的二叉树，您需要用至多 $p = \lfloor \log_2 n \rfloor$ 次询问找到树中的一个特殊节点 $s$。也就是说，$p$ 是满足 $2^p \le n$ 的最大整数。

每次询问包含两个不同的节点 $u$ 和 $v$。裁判程序会输出一个整数 $t$（$0 \le t \le 2$）表示询问的答案。令 $d(a, b)$ 表示从节点 $a$ 到节点 $b$ 的简单路径上有几条边。

• 若 $t = 0$，则节点 $u$ 离特殊节点更近。也就是说，$d(u, s) < d(v, s)$。
• 若 $t = 1$，则节点 $u$ 和节点 $v$ 到特殊节点的距离相同。也就是说，$d(u, s) = d(v, s)$。
• 若 $t = 2$，则节点 $v$ 离特殊节点更近。也就是说，$d(u, s) > d(v, s)$。

请注意：裁判程序是适应性的。也就是说，每组测试数据的答案不是事先确定的。裁判程序可以根据您的询问决定特殊节点，只要它的答案与之前的询问和答案不冲突即可。

输入格式

有多组测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$2 \le n \le 10^5$）表示二叉树中节点的数量。

对于接下来 $n$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$0 \le x_i, y_i \le n$），表示第 $i$ 个节点的左子节点和右子节点。若 $x_i = 0$，则第 $i$ 个节点没有左子节点；若 $y_i = 0$，则第 $i$ 个节点没有右子节点。

保证所有数据 $n$ 之和不超过 $2 \times 10^5$。

交互方式

要提出询问，请输出一行。首先输出 $\texttt{?}$，之后跟一个空格，然后输出两个不同的由单个空格分隔的整数 $u$ 和 $v$（$1 \le u, v \le n$）。在清空输出缓冲区之后，您的程序需要读入一个整数 $t$，表示对您的询问的回答。

要猜测特殊节点，请输出一行。首先输出 $\texttt{!}$，之后跟一个空格，然后输出一个整数 $s$（$1 \le s \le n$）表示特殊节点。在清空输出缓冲区之后，您的程序应该马上开始处理下一组测试数据。如果没有更多测试数据，您的程序应该立即退出。还请注意，猜测特殊节点不算一次询问。

清空输出缓冲区可以使用以下方式：

• C 和 C++ 使用 $\texttt{fflush(stdout)}$（如果您使用 $\texttt{printf}$）或 $\texttt{cout.flush()}$（如果您使用 $\texttt{cout}$）。
• Java 使用 $\texttt{System.out.flush()}$。
• Python 使用 $\texttt{stdout.flush()}$。

2
5
0 0
1 5
2 4
0 0
0 0

1

0

2
0 2
0 0

2

? 5 1

? 1 4

! 2



? 2 1

! 1