#include <bits/stdc++.h>

using namespace std;
#define SZ(x) (int) (x).size()
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(auto i = (a); i < (b); i++)
#define For(i, a, b, c) \
	for(auto i = (a); i != (b); i += (c))
#define REPR(i, n) for(auto i = (n) - 1; i >= 0; i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase(unique(ALL(v)), (v).end())
#define eb emplace_back

typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> PI;
typedef pair<ll, ll> PL;
const double EPS = 1e-6;
const int MOD = 1e9 + 7;
const int INF = (1 << 30);
const ll LINF = 1e18;
const double math_PI = acos(-1);

template<typename T>
vector<T> make_v(size_t a) {
	return vector<T>(a);
}

template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(
		a, make_v<T>(ts...));
}

template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(
	T &t, const V &v) {
	t = v;
}

template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(
	T &t, const V &v) {
	for(auto &e: t) fill_v(e, v);
}

template<class T>
bool chmax(T &a, const T &b) {
	if(a < b) {
		a = b;
		return true;
	}
	return false;
}

template<class T>
bool chmin(T &a, const T &b) {
	if(a > b) {
		a = b;
		return true;
	}
	return false;
}

template<typename S, typename T>
istream &operator>>(istream &is, pair<S, T> &p) {
	cin >> p.first >> p.second;
	return is;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &vec) {
	for(T &x: vec) is >> x;
	return is;
}

template<typename T>
string join(vector<T> &vec, string splitter) {
	stringstream ss;
	REP(i, SZ(vec)) {
		if(i != 0) ss << splitter;
		ss << vec[i];
	}
	return ss.str();
}

template<typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
	os << join(vec, " ");
	return os;
}

#ifdef LOCAL
#include "./cpp-dump/dump.hpp"
#include "./cpp-dump/mytypes.hpp"
#define dump(...) cpp_dump(__VA_ARGS__)
namespace cp = cpp_dump;
#else
#define dump(...)
#define preprocess(...)
#define CPP_DUMP_SET_OPTION(...)
#define CPP_DUMP_DEFINE_EXPORT_OBJECT(...)
#define CPP_DUMP_DEFINE_EXPORT_ENUM(...)
#define CPP_DUMP_DEFINE_DANGEROUS_EXPORT_OBJECT(...)
#endif
template<class T = ll>
struct Edge {
public:
	int from, to;
	T cost;
	Edge() {
	}
	Edge(int _from, int _to, T _cost) {
		from = _from;
		to = _to;
		cost = _cost;
	}
};
template<class T = ll>
using Edges = vector<Edge<T>>;
template<class T = ll>
using Graph = vector<Edges<T>>;

int query(int a, int b) {
	cout << "?" << " " << a + 1 << " " << b + 1 << endl;
	int ret;
	cin >> ret;
	return ret;
}

void answer(int a) {
	cout << "! " << a + 1 << endl;
}

void solve() {
	int N;
	cin >> N;
	Graph<> G(N);
	REP(i, N) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		if(a != -1) {
			G[a].emplace_back(a, i, 1);
			G[i].emplace_back(i, a, 1);
		}
		if(b != -1) {
			G[b].emplace_back(b, i, 1);
			G[i].emplace_back(i, b, 1);
		}
	}
	int k = 0;
	vb removed(N);
	int cand = N;

	auto dfs_remove = [&](auto f, int cur, int pre) -> void {
		if(removed[cur]) return;
		removed[cur] = true;
		cand--;
		for(auto e: G[cur]) {
			if(e.to == pre) continue;
			if(removed[e.to]) continue;
			f(f, e.to, cur);
		}
	};
	while(cand > 2) {
		vector<PI> childs;
		auto dfs = [&](auto f, int cur, int pre) -> PI {
			int s = 1;
			bool flag = true;
			vector<PI> c;
			for(auto e: G[cur]) {
				if(e.to == pre) continue;
				if(removed[e.to]) continue;
				PI v = f(f, e.to, cur);
				if(v.first >= 0) return { v.first, -1 };
				if(v.second > cand / 2) {
					flag = false;
				}
				c.emplace_back(v.second, e.to);
				s += v.second;
			}
			if(pre >= 0 && !removed[pre]) {
				c.emplace_back(cand - s, pre);
			}
			if(cand - s > cand / 2) flag = false;
			if(flag) {
				childs = c;
				return { cur, -1 };
			}
			return { -1, s };
		};
		int v = dfs(dfs, k, -1).first;
		dump(v, childs);
		if(SZ(childs) == 2) {
			int t = query(childs[0].second, childs[1].second);
			if(t == 1) {
				answer(v);
				return;
			} else if(t == 0) {
				removed[v] = true;
				cand--;
				dfs_remove(dfs_remove, childs[1].second, v);
				k = childs[0].second;
			} else {
				removed[v] = true;
				cand--;
				dfs_remove(dfs_remove, childs[0].second, v);
				k = childs[1].second;
			}
		} else {
			so(childs);
			int t = query(childs[1].second, childs[2].second);
			if(t == 1) {
				dfs_remove(dfs_remove, childs[1].second, v);
				dfs_remove(dfs_remove, childs[2].second, v);
				k = v;
			} else if(t == 0) {
				removed[v] = true;
				cand--;
				dfs_remove(dfs_remove, childs[0].second, v);
				dfs_remove(dfs_remove, childs[2].second, v);
				k = childs[1].second;
			} else {
				removed[v] = true;
				cand--;
				dfs_remove(dfs_remove, childs[0].second, v);
				dfs_remove(dfs_remove, childs[1].second, v);
				k = childs[2].second;
			}
		}
		dump(k, cand, removed);
	}
	vi c;
	REP(i, N) {
		if(!removed[i]) c.push_back(i);
	}
	if(cand == 1) {
		answer(c[0]);
		return;
	}
	int t = query(c[0], c[1]);
	if(t == 0) {
		answer(c[0]);
	} else {
		answer(c[1]);
	}
	return;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while(T--) {
		solve();
	}
	return 0;
}