题目背景

原题链接：https://oier.team/problems/X12D。

题目描述

这是一道交互题。

有一棵 $n$ 个点的树，树的形态给定，树上有一个隐藏点 $s$，你每次可以给出一个点 $u$，交互库选择将 $s$ 向 $u$ 移动一步（若 $s=u$ 则无事发生），或者返回目前 $u$ 到 $s$ 的距离。交互库会告诉你他选择的操作，如果选择的是操作 $2$ 会告诉你距离。你需要在 $m$ 次询问内求出目前 $s$ 的位置。

每个测试点中有 $T$ 组测试数据。

交互库不自适应，这意味着询问开始前 $s$ 的位置确定，与你的询问无关。

【交互方式】

首先输入一个正整数 $T$ 表示测试数据组数。

接下来 $T$ 组数据，每组数据的第一行输入两个正整数 $n,m$ 分别表示树的点数和询问次数限制，接下来 $n-1$ 行每行两个数 $u,v$ 表示树上存在一条连接 $u,v$ 的边。

接着你需要进行交互，询问格式为 ? u，其中需要满足 $1 \leq u \leq n$，如果你本组数据的询问次数超过 $m$，交互库输出 -1，此时你需要立即结束程序否则之后交互库行为未定义。若询问次数未超过限制，交互库输出 1 或者 2 d，分别表示交互库选择将 $s$ 向 $u$ 移动一步或者告诉你 $s$ 到 $u$ 目前的距离为 $d$。当你确定 $s$ 目前的位置后，输出 ! u 表示 $s$ 目前在编号为 $u$ 的节点上。如果你的回答是正确的，交互库输出 1 并进入下一组测试数据，否则交互库输出 0，你需要立即结束程序否则之后交互库行为未定义。

你需要在你的每次输出后刷新缓冲区。

你可以使用如下语句来清空缓冲区：

• 对于 C/C++：fflush(stdout)；
• 对于 C++：std::cout << std::flush；
• 对于 Java：System.out.flush()；
• 对于 Python：stdout.flush()；
• 对于 Pascal：flush(output)；
• 对于其他语言，请自行查阅对应语言的帮助文档。

当你在单个测试点内总询问次数不超过 $\sum m$ 次时，保证交互库占用时间不超过 $1.5$ s，占用空间不超过 $50$ MiB，也就是说你的程序至少可以使用 $1.5$ s 的时间和 $462$ MiB 的空间。

输入格式

见【交互方式】。

输出格式

见【交互方式】。

1
4 200
1 2
2 4
2 3
1
1
1

? 2
? 2
! 2

2
5 200
5 1
4 2
2 3
2 1
1
2 1
2 0
1
6 200
6 1
2 1
4 2
4 5
3 2
2 3
2 1
1
1
1

? 2
? 2
? 1
! 1
? 6
? 2
? 4
? 4
! 4

提示

【样例解释 #1】

对于样例 $1$，初始有 $s=3$，询问两次点 $2$，第一次交互库返回 $1$，并将 $s$ 向点 $2$ 移动一步，$s=2$，第二次询问交互库返回 $1$，$s=2$，所以 $s$ 不发生变化。此时可以确定 $s=2$，回答 $s=2$ 后，交互库返回 $1$ 表示答案正确。

【数据范围】

本题使用捆绑测试。

子任务编号	$T \leq$	$n \leq$	$m =$	特殊性质	分值	子任务依赖
$1$	$500$	$10$	$200$	无	$5$	无
$2$	$10$	$1000$	$3n$		$13$	$1$
$3$	$10^4$	$10^5$	$n-1$	A	$7$	无
$4$				B	$10$
$5$			$3n$	C	$14$
$6$			$2n$	无	$21$	$1,2,5$
$7$			$n-1$		$30$	$1,2,3,4,5,6$

特殊性质 A：树上每个点度数不大于 $2$。

特殊性质 B：树上只有至多一个点度数大于 $1$。

特殊性质 C：树的生成方式为：对于每个 $2 \leq i \leq n$，等概率随机选取 $[1,i)$ 中的一个整数 $x$，将 $x$ 与 $i$ 连边。

对于所有数据，$1 \leq T \leq 10^4$，$1 \leq \sum n \leq 10^5$，$m\geq n-1$。