#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
 
int n,x,CNT;

inline int query(int a,int b){
    if(a<1||a>n||b<1||b>n){
        cout<<"! "<<"-1"<<endl;
        exit(0);
    }

    CNT++;

    cout<<"? "<<a<<" "<<b<<endl;
    cin>>x;
    return x;
}

inline void solve(){
    cin>>n;

    CNT=0;
    int lim=log2(n);

    vector<vector<int> >g(n+1);
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        if(a)g[i].push_back(a),g[a].push_back(i);
        if(b)g[i].push_back(b),g[b].push_back(i);
    }

    vector<int>mx(n+1),sz(n+1),f(n+1);
    mx[0]=inf;

    int sum=n,rt=0;

    auto find=[&](auto self,int u,int fa)->void {
        sz[u]=1,mx[u]=0;
        for(auto t:g[u]){
            if(t==fa||f[t])continue;
            self(self,t,u);
            sz[u]+=sz[t];
            mx[u]=max(mx[u],sz[t]);
        }
        mx[u]=max(mx[u],sum-sz[u]);
        if(mx[u]<mx[rt])rt=u;
    };
    find(find,1,-1);

    auto dfs=[&](auto self,int u,int fa)->void {
        sz[u]=1;
        for(auto t:g[u]){
            if(t==fa||f[t])continue;
            self(self,t,u);
            sz[u]+=sz[t];
        }
    };

    int ans=-1;

    auto wk=[&](auto self,int u)->void {
        dfs(dfs,u,-1);
        
        int cnt=0;
        for(auto t:g[u]){
            if(f[t])continue;
            cnt++;
        }

        if(cnt==0){
            ans=u;
            return;
        }

        if(cnt==1){
            for(auto t:g[u]){
                if(f[t])continue;

                if(CNT==lim){
                    ans=1e9;
                    return;
                }

                ans=(query(t,u)==0?t:u);
                return;
            }
        }

        int son1=-1,son2=-1;
        for(auto t:g[u]){
            if(f[t])continue;

            if(son1==-1)son1=t;
            else son2=t;
        }

        if(CNT==lim){
            ans=1e9;
            return;
        }

        int x=query(son1,son2);

        if(x==0){
            f[u]=1;
            sum=sz[son1],rt=0;
            find(find,son1,-1);
            self(self,son1);
        }else if(x==2){
            f[u]=1;
            sum=sz[son2],rt=0;
            find(find,son2,-1);
            self(self,son2);
        }else{
            int son=-1;
            for(auto t:g[u]){
                if(f[t]||t==son1||t==son2)continue;
                son=t;
            }
            if(son==-1){
                ans=u;
                return;
            }

            f[son1]=f[son2]=1;
            sum=sz[son]+1,rt=0;
            find(find,u,-1);
            self(self,u);
        }
    };
    wk(wk,rt);

    cout<<"! "<<ans<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    // cout<<setiosflags(ios::fixed)<<setprecision(10);

    int t=1;
    cin>>t;
    while(t--)solve();

    return 0;
}