#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long

const int mxn = 2e5+1;

int n,sub[mxn],vis[mxn];
vector<int> adj[mxn];

int siz;

int dfs(int v) {
	if (vis[v]) return 0;
	vis[v] = 1;
	sub[v] = 1;
	int mx = 0;
	int res = 0;
	for (int u : adj[v]) {
		if (!vis[u]) {
			res = max(res,dfs(u));
			sub[v] += sub[u];
			mx = max(mx,sub[u]);
		}
	}
	mx = max(mx,siz-sub[v]);
	if (siz/2 >= mx) res = v;
	return res;
}

void solve() {
	cin>>n;
	for (int i=1; i<=n; i++) {
		adj[i].clear();
	}
	for (int i=1; i<=n; i++) {
		int u,v; cin>>u>>v;
		if (u) adj[i].push_back(u);
		if (v) adj[i].push_back(v);
		if (u) adj[u].push_back(i);
		if (v) adj[v].push_back(i);
//		cout<<u<<" "<<v<<endl;
	}
	
	siz = n;
	int crt = 1;
	while (siz > 1) {
		for (int i=1; i<=n; i++) vis[i] = 0;
		int rt = dfs(crt);
		cout<<rt<<"\n";
		if (sz(adj[rt]) == 3) {
			int u1 = adj[rt][0];
			int u2 = adj[rt][1];
			int u3 = adj[rt][2];
			
			int s1 = sub[u1]; if (s1 > sub[rt]) s1 = siz - sub[rt];
			int s2 = sub[u2]; if (s2 > sub[rt]) s2 = siz - sub[rt];
			int s3 = sub[u3]; if (s3 > sub[rt]) s3 = siz - sub[rt];
			/*
			cout<<u1<<" "<<u2<<" "<<u3<<"..."<<s1<<" "<<s2<<" "<<s3<<endl;;
			cout<<rt<<" "<<sub[rt]<<endl;
			cout<<sub[u1]<<" "<<sub[u2]<<" "<<sub[u3]<<endl;
			*/
			int mins = min(s1,min(s2,s3));
			
			int v1,v2,v3;
			if (s3 == mins) {
				v1 = u1, v2 = u2, v3 = u3;
			} else if (s2 == mins) {
				v1 = u1, v2 = u3, v3 = u2;
			} else if (s1 == mins) {
				v1 = u2, v2 = u3, v3 = u1;
			}
			
		//	cout<<"? "<<v1<<" "<<v2<<endl;
		//	cout<<v1<<" "<<v2<<" "<<v3<<" "<<s1<<" "<<s2<<" "<<s3<<"\n";
			int t; cin>>t;
			if (t==0) {
				crt = v1;
				adj[v1].erase(find(all(adj[v1]),rt));
				if (u1==v1) siz=s1;
				else if (u2==v1) siz = s2;
				else if (u3==v1) siz = s3;
			} else if (t==1) {
				crt = rt;
				adj[rt].erase(find(all(adj[rt]),v1));
				adj[rt].erase(find(all(adj[rt]),v2));
				if (u1==v3) siz=s1+1;
				else if (u2==v3) siz = s2+1;
				else if (u3==v3) siz = s3+1;
		//		cout<<siz<<endl
			} else if (t==2) {
				crt = v2;
				adj[v2].erase(find(all(adj[v2]),rt));
				if (u1==v2) siz=s1;
				else if (u2==v2) siz = s2;
				else if (u3==v2) siz = s3;
			}
		} else if (sz(adj[rt]) == 2) {
			int u1 = adj[rt][0]; 
			int u2 = adj[rt][1]; 
			
			int s1 = sub[u1]; if (s1 > sub[rt]) s1 = siz - sub[rt];
			int s2 = sub[u2]; if (s2 > sub[rt]) s2 = siz - sub[rt];
			
			cout<<"? "<<u1<<" "<<u2<<endl;
			int t; cin>>t;
			if (t==0) {
				crt = u1;
				adj[u1].erase(find(all(adj[u1]),rt));
				siz = s1;
			} else if (t==1) {
				crt = rt;
				siz = 1;
			} else if (t==2) {
				crt = u2;
				adj[u2].erase(find(all(adj[u2]),rt));
				siz = s2;
			}
		} else if (sz(adj[rt]) == 1) {
			int u1 = rt;
			int u2 = adj[rt][0];
			assert(siz==2);
			cout<<"? "<<u1<<" "<<u2<<endl;
			int t; cin>>t;
			if (t==0) {
				siz = 1;
				crt = u1;
			} else if (t==2) {
				siz = 1;
				crt = u2;
			} else {
				cout<<"WTF";
			}
		}
	}
	cout<<"! "<<crt<<endl;
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	
	int t; cin>>t;
	while (t--) {
		solve();
	}
	
}