#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2000010;
vector<int> adj[N];
int del[N],siz[N],csiz[N];
void solve(){
	int cntq=0;
	int n;
	cin>>n;
	for(int i=0;i<=n;i++){
		adj[i].clear();
		siz[i]=0;
		del[i]=0;
		csiz[i]=0;
	}
	// vector<vector<int>> adj(n+10);
	for(int i=1;i<=n;i++){
		int x,y;
		cin>>x>>y;
		if(x){
			adj[i].push_back(x);
			adj[x].push_back(i);
		}
		if(y){
			adj[i].push_back(y);
			adj[y].push_back(i);
		}
	}
	vector<int> zx;
	int cn=n;
	auto get=[&](auto &&self,int u,int la)->void{
		if(u<0||u>n){/////
			exit(0);
		}
		siz[u]=1;
		int res=0;
		int c=0;
		vector<int> cur;
		if(u<0||u>n){/////
			exit(0);
		}
		for(auto x:adj[u]){
			if(x<0||x>n){/////
				exit(0);
			}
			if(x==la||del[x])
				continue;
			self(self,x,u);
			siz[u]+=siz[x];
			res=max(res,siz[x]);
			cur.push_back(x);
			c++;
		}
		if(cn-siz[u]>0){
			c++;
			cur.push_back(la);
		}
		res=max(res,cn-siz[u]);
		if(res*2<=cn){
			if(c==3&&zx.empty()){
				csiz[cur[0]]=siz[cur[0]];
				csiz[cur[1]]=siz[cur[1]];
				csiz[cur[2]]=cn-siz[u];
			}
			zx.push_back(u);
		}
	};
	auto de=[&](auto &&self,int u,int la)->void{
		if(u<0||u>n){/////
			exit(0);
		}		
		del[u]=1;
		cn--;
		for(auto x:adj[u]){
			if(x==la||del[x])
				continue;
			self(self,x,u);
		}
	};
	int id=1;
	while(true){
		zx.clear();
		while(id<=n&&del[id])
			id++;
		if(id<0||id>n){/////
			exit(0);
		}
		if(cn <= 1){
			cout<<"! "<<id<<endl;
			return;
		}

		get(get,id,0);

		if(zx.empty())
			break;
		int z=zx[0];
		int cnt=0;
		vector<int> cur;
		for(auto x:adj[z]){
			if(!del[x]){
				cnt++;
				cur.push_back(x);
			}
		}
		if(cnt==3){
			cntq++;
			// assert((1<<cntq)<=n);

			sort(cur.begin(),cur.end(),[&](int x,int y){
				return csiz[x]>csiz[y];
			});

			cout<<"? "<<cur[0]<<" "<<cur[1]<<endl;
			int g;
			cin>>g;
			if(g==0){
				de(de,cur[1],z);
				de(de,cur[2],z);
			}
			else if(g==1){
				de(de,cur[1],z);
				de(de,cur[0],z);
			}
			else{
				de(de,cur[0],z);
				de(de,cur[2],z);
			}
			if(g != 1)
			{
				cn--;
				del[z] = 1;
			}
		}
		else if(cnt==2){
			cntq++;
			// assert((1<<cntq)<=n);			
			cout<<"? "<<cur[0]<<" "<<cur[1]<<endl;
			int g;
			cin>>g;
			if(g==0){
				de(de,cur[1],z);
			}
			else if(g==1){
				cout<<"! "<<z<<endl;
				return;
			}
			else{
				de(de,cur[0],z);
			}
			cn--;
			del[z] = 1;
		}
		else if(cnt == 1){
			cntq++;		
			cout<<"? "<<cur[0]<<" "<<z<<endl;
			int g;
			cin>>g;
			if(g==0){
				cout<<"! "<<cur[0]<<endl;
				return;
			}		
			else{
				cout<<"! "<<z<<endl;
				return;
			}
		}
		else
			break;
	}
	cout<<"! "<<1<<endl;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}