G. Binary Tree

#include <bits/stdc++.h>
using namespace std;
vector<int>a[100005];
int root,p,val,s[100005],cnt[100005],va[100005],dep,n;
int query(int u,int v)
{
    int x;
    cout<<"?"<<" "<<u<<" "<<v<<endl;
    cin>>x;
    return x;
}
void dfs1(int n1,int fa)
{
    s[n1]=1;
    int maxn=0;
    for(int i=0;i<a[n1].size();i++)
    {
        if(cnt[a[n1][i]]==dep&&a[n1][i]!=fa)
        {
            dfs1(a[n1][i],n1);
            s[n1]+=s[a[n1][i]];
            maxn=max(maxn,s[a[n1][i]]);
        }
    }
    maxn=max(maxn,n-s[n1]);
    if(maxn<val)
    {
        p=n1;
        val=maxn;
        for(int i=0;i<a[n1].size();i++)
	    {
	        if(cnt[a[n1][i]]==dep&&a[n1][i]!=fa)
	        {
	            va[a[n1][i]]=s[a[n1][i]];
	        }
	    }
        va[fa]=n-s[n1];
    }
}
void dfs2(int n1,int fa)
{
    cnt[n1]++;
    n++;
    for(int i=0;i<a[n1].size();i++)
    {
        if(cnt[a[n1][i]]==dep&&a[n1][i]!=fa)
        {
            dfs2(a[n1][i],n1);
        }
    }
}
bool cmp(int a,int b)
{
	return va[a]<va[b];
}
void solve()
{
    while(1)
    {
        p=root;
        val=n;
        dfs1(root,0);
        int m=0,f[5];
        for(int i=0;i<a[p].size();i++)
        {
            if(cnt[a[p][i]]==dep)
            {
                f[m++]=a[p][i];
            }
        }
        sort(f,f+m,cmp);
        if(m==3)
        {
        	swap(f[0],f[1]);
            f[1]=p;
            int x=query(f[0],f[2]);
            root=f[x];
            if(x==1)
            {
                cnt[f[0]]=-1;
                cnt[f[2]]=-1;
            }
        }
        else if(m==2)
        {
            f[2]=f[1];
            int x=query(f[0],f[2]);
            if(x==1)
            {
                cout<<"!"<<" "<<p<<endl;
                return;
            }
            root=f[x];
        }
        else if(m==1)
        {
            f[2]=p;
            int x=query(f[0],f[2]);
            cout<<"!"<<" "<<f[x]<<endl;
            return;
        }
        else if(m==0)
        {
            cout<<"!"<<" "<<p<<endl;
            return;
        }
        n=0;
        dfs2(root,p);
        dep++;
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            a[i].clear();
            cnt[i]=0;
        }
        for(int i=1;i<=n;i++)
        {
            int u,v;
            cin>>u>>v;
            if(u)
            {
                a[u].push_back(i);
                a[i].push_back(u);
            }
            if(v)
            {
                a[v].push_back(i);
                a[i].push_back(v);
            }
        }
        root=1;
        dep=0;
        solve();
    }
    return 0;
}