rt 一开始 wa 了之后我甚至还照着题解重构了一遍 然后…

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;

const int MAXN = 100005;

int T, n, Q, fa[MAXN];
int ctn, cte;
int dfn[MAXN], dfe[MAXN];
int idn[MAXN], ide[MAXN];
class Graph {
	private : 
	struct edge {
		int to, nex;
	}e[MAXN << 1]; int idx;
	public : 
	int head[MAXN];
	inline edge operator [] (const int &x) const {
		return e[x];
	}
	inline void add(int u, int v) {
		e[++ idx].to = v;
		e[idx].nex = head[u];
		head[u] = idx;
	}
	inline void Clear() {
		for (int i = 1; i <= n; ++ i)
			head[i] = 0;
		for (int i = 1; i <= idx; ++ i)
			e[i].to = e[i].nex = 0;
		idx = 0;
	}
}G;

inline void dfs(int u) {
	idn[dfn[u] = ++ ctn] = u;
	for (int i = G.head[u]; i; i = G[i].nex) {
		int v = G[i].to;
		if (v == fa[u]) continue;
		fa[v] = u; dfs(v);
	}
	ide[dfe[u] = ++ cte] = u;
}
inline int Get_lca(int u, int v) {
	while (u != v) {
		if (dfn[u] < dfn[v]) swap(u, v); 
		u = fa[u];
	}
	return u;
}

inline int Query(int tp, int l, int r) {
	if (l > r) return n;
	printf ("? %d %d %d\n", tp, l, r);
	int res; fflush(stdout);
	scanf ("%d", &res); return res;
}

inline void Solve() {
	scanf ("%d%d", &n, &Q);
	for (int i = 1; i < n; ++ i) {
		int u, v;
		scanf ("%d%d", &u, &v);
		G.add(u, v); G.add(v, u);
	}
	ctn = cte = 0; dfs(1);
	for (int i = 1; i <= n; ++ i) 
		printf ("%d ", idn[i]); puts("");
	for (int i = 1; i <= n; ++ i) 
		printf ("%d ", ide[i]); puts(""); 
	fflush(stdout);
	while (Q --) {
		int u, v, lca;
		scanf ("%d%d", &u, &v); lca = Get_lca(u, v);
		if (dfn[u] > dfn[v]) swap(u, v);
		if (u == lca) {
			int ans = Query(1, 1, dfn[u] - 1);
			ans = min(ans, Query(1, dfn[v] + 1, n));
			ans = min(ans, Query(2, 1, dfe[v] - 1));
			printf ("! %d\n", ans);
		} else {
			int t = 0, lst = 0;
			for (int i = G.head[lca]; i; i = G[i].nex) {
				if (dfn[G[i].to] > dfn[v]) break;
				lst = t, t = G[i].to;
			}
			int ans = Query(1, 1, dfn[lca] - 1);
			ans = min(ans, Query(2, 1, dfe[u] - 1));
			ans = min(ans, Query(1, dfn[u] + 1, dfn[t] - 1));
			ans = min(ans, Query(2, dfe[lst] + 1, dfe[v] - 1));
			ans = min(ans, Query(1, dfn[v] + 1, n));
			printf ("! %d\n", ans);
		}
		fflush(stdout); scanf ("%d", &u);
		if (u != 1) exit(0);
	}
}

int main()
{
	scanf ("%d", &T);
	while (T --) Solve();
	return 0;
}