题目描述

这是一个交互式问题。

给定一个包含 $n$ 个顶点的二叉树，你的任务是在最多 $p = \lfloor \log_2 n \rfloor$ 次查询内找到树中的一个特殊顶点 $s$。也就是说，$p$ 是满足 $2^p \leq n$ 的最大整数。

每次查询包括两个不同的顶点 $u$ 和 $v$。交互器会输出一个整数 $t$（$0 \leq t \leq 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 \leq n \leq 10^5$），表示二叉树的顶点数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$0 \leq x_i, y_i \leq n$），表示第 $i$ 个顶点的左子节点和右子节点。如果 $x_i = 0$，则第 $i$ 个顶点没有左子节点；如果 $y_i = 0$，则第 $i$ 个顶点没有右子节点。

保证所有测试用例的顶点总数不超过 $2 \times 10^5$。

交互协议

为了进行查询，输出一行。首先输出 ? 后接一个空格，然后打印两个不同的整数 $u$ 和 $v$（$1 \leq u, v \leq n$），用空格分隔。在刷新输出后，你的程序需要读取一个单个整数 $t$，表示查询的答案。

如果你想猜测特殊顶点，输出一行。首先输出 ! 后接一个空格，然后打印一个整数 $s$（$1 \leq s \leq n$），表示特殊顶点。在刷新输出后，你的程序应该继续处理下一个测试用例，或者如果没有更多测试用例则立即退出。注意，你的猜测不计入查询次数。

为了刷新输出，你可以使用：

• 在 C 和 C++ 中使用 fflush(stdout) 或 cout.flush()。
• 在 Java 中使用 System.out.flush()。
• 在 Python 中使用 stdout.flush()。

如果你的评测结果为Runtime Error，大概是你询问的次数超过了$\lfloor \log_2 n \rfloor$

样例

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