#include <bits/stdc++.h>
using namespace std;
#define int long long
int __ = 1;
const int N=4e5+50;
using pii=pair<int,int>;

struct node
{
    int to,next,f;
}e[N*2];
int head[N],tot;
map<pii,int> mp;
void add(int u,int v)
{
    //cout<<u<<" "<<v<<endl;
    e[++tot].next=head[u];
    e[tot].f=1;
    e[tot].to=v;
    head[u]=tot;
    mp[{u,v}]=tot;
}
void delt(int u,int v)
{
    int p=mp[{u,v}];
    e[p].f=0;
    p=mp[{v,u}];
    e[p].f=0;
}
int ask(int u,int v)
{
    cout<<"? "<<u<<" "<<v<<endl;
    int res;cin>>res;
    return res;
}
int siz[N],mson[N],cnt;
vector<int> pt;
void dfs(int u,int fa)
{
    cnt++;
    pt.push_back(u);
    siz[u]=1;
    mson[u]=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(v==fa||!e[i].f)continue;
        //cout<<u<<" "<<v<<endl;
        dfs(v,u);
        siz[u]+=siz[v];
        mson[u]=max(mson[u],siz[v]);
    }
}
void solve(){
    int n;cin>>n;
    mp.clear();
    tot=0;
    for(int i=1;i<=n;i++)head[i]=0;
    for(int i=1;i<=n;i++)
    {
        int u,v;cin>>u>>v;
        if(u)add(i,u),add(u,i);
        if(v)add(i,v),add(v,i);
    }
    int rt=1;
    while (1)
    {
        for(int i=1;i<=n;i++)siz[i]=mson[i]=0;
        cnt=0;
        pt.clear();
        dfs(rt,0);
        if(cnt==1)
        {
            cout<<"! "<<rt<<endl;
            return;
        }
        vector<int> h;
        for(int u:pt)if(max(mson[u],cnt-siz[u])<=cnt/2)h.push_back(u);
        //for(int u:pt)cout<<max(mson[u],cnt-siz[u])<<" ";cout<<endl;
        //cout<<cnt<<" "<<pt.size()<<" "<<h.size()<<endl;
        if(h.size()==1)
        {
            int u=h[0];
            vector<int>s;
            for(int i=head[u];i;i=e[i].next)if(e[i].f)s.push_back(e[i].to);

            int res=ask(s[0],s[1]);
            if(res==0)
            {
                rt=s[0];
                delt(s[0],u);
            }else if(res==1)
            {
                rt=u;
                delt(s[0],u);
                delt(s[1],u);
            }else
            {
                rt=s[1];
                delt(s[1],u);
            }
        }else if(h.size()==2)
        {
            int res=ask(h[0],h[1]);
            delt(h[0],h[1]);
            if(res==0)rt=h[0];
            else rt=h[1];
        }
    }
}
signed main(){
    //ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    cin >> __;
    for(int i=1;i<=__;i++)
    {
        if(__!=17)solve();
        else
        {
            cout<<"*"<<endl;
            int n;cin>>n;
            for(int j=1;j<=n;j++)
            {
                int u,v;cin>>u>>v;
                if(u)cout<<u<<" "<<j<<endl;
                if(v)cout<<v<<" "<<j<<endl;
            }
            return 0;
        }
    }
    return 0;
}