### 题目描述
这是问题的困难版本。唯一的区别是查询数量的限制。

这是一道交互题。

给你一棵由 $n$ 个节点组成的树，其中节点 $1$ 为根节点。

其中一个节点中有一个隐藏的鼹鼠。要找到它的位置，你可以选择一个整数 $x(1\le x\le n)$ 进行询问。接下来，当鼹鼠在子树 $x$ 中时，交互机将返回 $1$ 。否则，交互机将返回 $0$ 。如果判断返回 $0$ ，并且鼹鼠不在根节点 $1$ 中，则鼹鼠将移动到其当前所在节点的父节点。

最多使用 $160$ 次操作来查找鼹鼠所在的节点。
### 输入格式
每个测试包含多个测试用例。第一行包含测试用例的数量 $t(1\le t\le 100)$。测试用例的描述如下。
### 输出格式
每个测试用例的第一行包含一个整数$n(2\le n\le 5000)$。
以下 $n-1$ 行描述了树的边。每行包含两个空格分隔的整数 $u_i$ 和 $v_i(1\le u_i,v_i\le n)$，表示节点 $u_i$ 和 $v _i$ 之间有一条边。

可以保证输入数据是一棵树。

此任务中的交互器不是自适应的。换句话说，鼹鼠最初所在的节点在每个测试用例中都是固定的，在交互过程中不会改变。

要提出查询，您需要选择一个顶点 $x(1 \le x \le n)$ 并输出以下格式的行：
- "? x"

之后，交互机将返回：

- $0$ 如果鼹鼠不在子树$x$中；

- $1$ 如果鼹鼠在子树$x$中。

对于每个测试用例，您最多可以进行 $160$ 次查询。

接下来，如果你的程序找到了鼹鼠所在的当前节点，请打印以下格式的行：
- "! x"

请注意，此行不被视为查询，在计算查询数量时也不会被考虑在内。

在此之后，继续进行下一个测试用例。

如果您在交互过程中进行了超过 $160$ 次查询，您的程序必须立即终止，程序将会  WA。

输出测试用例的查询或答案后，不要忘记输出行尾 "\n" 并刷新输出。否则，程序将会 ILE。为此，请使用：

- C++中的fflush(stdout)或cout.flush()；
- Java中的System.out.flush()；
- Pascal中的flush(output)；
- Python中的stdout.flush()；
- 请参阅其他语言的文档。
### 提示
在第一个测试用例中，鼹鼠最初位于节点 $2$ 中。

对于查询 "? 2"，交互机返回 $1$ ，因为鼹鼠在子树中 $2$ 。查询后，鼹鼠不会移动。

答案 $2$ 是鼹鼠所在的当前节点，因此答案被认为是正确的。

在第二个测试用例中，鼹鼠最初位于节点$6$中。

对于查询 "? 2"，交互机返回 $0$，因为鼹鼠不在子树 $2$ 中。查询后，鼹鼠从节点 $6$ 移动到节点 $5$ 。

对于查询 "? 6"，交互机返回 $0$，因为鼹鼠不在子树$6$中。查询后，鼹鼠从节点 $5$ 移动到节点 $4$。

对于查询 "? 4"，交互机返回$1$，因为鼹鼠在子树 $4$ 中。查询后，鼹鼠不会移动。

答案 $4$ 是鼹鼠所在的当前节点，因此答案被认为是正确的。

请注意，该示例仅用于理解语句，示例中的查询不能保证确定鼹鼠的唯一位置。

题目描述

这是问题的困难版本。唯一的区别是查询数量的限制。

这是一道交互题。

给你一棵由 $n$ 个节点组成的树，其中节点 $1$ 为根节点。

其中一个节点中有一个隐藏的鼹鼠。要找到它的位置，你可以选择一个整数 $x(1\le x\le n)$ 进行询问。接下来，当鼹鼠在子树 $x$ 中时，交互机将返回 $1$ 。否则，交互机将返回 $0$ 。如果判断返回 $0$ ，并且鼹鼠不在根节点 $1$ 中，则鼹鼠将移动到其当前所在节点的父节点。

最多使用 $160$ 次操作来查找鼹鼠所在的节点。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t(1\le t\le 100)$。测试用例的描述如下。

输出格式

每个测试用例的第一行包含一个整数$n(2\le n\le 5000)$。 以下 $n-1$ 行描述了树的边。每行包含两个空格分隔的整数 $u_i$ 和 $v_i(1\le u_i,v_i\le n)$，表示节点 $u_i$ 和 $v _i$ 之间有一条边。

可以保证输入数据是一棵树。

此任务中的交互器不是自适应的。换句话说，鼹鼠最初所在的节点在每个测试用例中都是固定的，在交互过程中不会改变。

要提出查询，您需要选择一个顶点 $x(1 \le x \le n)$ 并输出以下格式的行：

• "? x"

之后，交互机将返回：

• $0$ 如果鼹鼠不在子树$x$中；

• $1$ 如果鼹鼠在子树$x$中。

对于每个测试用例，您最多可以进行 $160$ 次查询。

接下来，如果你的程序找到了鼹鼠所在的当前节点，请打印以下格式的行：

• "! x"

请注意，此行不被视为查询，在计算查询数量时也不会被考虑在内。

在此之后，继续进行下一个测试用例。

如果您在交互过程中进行了超过 $160$ 次查询，您的程序必须立即终止，程序将会 WA。

输出测试用例的查询或答案后，不要忘记输出行尾 "\n" 并刷新输出。否则，程序将会 ILE。为此，请使用：

• C++中的fflush(stdout)或cout.flush()；
• Java中的System.out.flush()；
• Pascal中的flush(output)；
• Python中的stdout.flush()；
• 请参阅其他语言的文档。

提示

在第一个测试用例中，鼹鼠最初位于节点 $2$ 中。

对于查询 "? 2"，交互机返回 $1$ ，因为鼹鼠在子树中 $2$ 。查询后，鼹鼠不会移动。

答案 $2$ 是鼹鼠所在的当前节点，因此答案被认为是正确的。

在第二个测试用例中，鼹鼠最初位于节点$6$中。

对于查询 "? 2"，交互机返回 $0$，因为鼹鼠不在子树 $2$ 中。查询后，鼹鼠从节点 $6$ 移动到节点 $5$ 。

对于查询 "? 6"，交互机返回 $0$，因为鼹鼠不在子树$6$中。查询后，鼹鼠从节点 $5$ 移动到节点 $4$。

对于查询 "? 4"，交互机返回$1$，因为鼹鼠在子树 $4$ 中。查询后，鼹鼠不会移动。

答案 $4$ 是鼹鼠所在的当前节点，因此答案被认为是正确的。

请注意，该示例仅用于理解语句，示例中的查询不能保证确定鼹鼠的唯一位置。