#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10,INF = 1e9;
int T,n,vis[N];
vector<int> e[N];

void link(int x,int y){e[x].push_back(y); e[y].push_back(x);}

int dep[N],x,y,dx[N],dy[N],sz[N],fa[N];
vector<int> o;

void dfs(int u){
    o.push_back(u);
    sz[u] = 1;
    for(auto v : e[u])if(v != fa[u] && vis[v]){
        dep[v] = dep[u] + 1; fa[v] = u;
        dfs(v); 
        sz[u] += sz[v];
    }
}

int all;
int W(int x,int y){
    if(fa[x] == y)return sz[x];
    else return all - sz[y];
}

void solve(){
    scanf("%d",&n); int num = 0;
    for(int i=1;i<=n;i++)e[i].clear(),vis[i] = 1;
    for(int i=1;i<=n;i++){
        int x,y; scanf("%d%d",&x,&y);
        if(x)link(i,x); if(y)link(i,y);
    }
    while(1){
        int cnt = 0,ans = 0;
        for(int i=1;i<=n;i++)if(vis[i])cnt++,ans = i;
        if(cnt == 1){
            printf("! %d\n",ans); fflush(stdout);
            return;
        }
        x = y = 0; o.clear(); int rw = INF;
        fa[ans] = 0; dfs(ans); all = sz[ans];
        for(auto u : o){
            for(auto v : e[u])if(vis[v]){
                int w = max(W(u,v),W(v,u));
                if(rw > w){
                    rw = w; x = u,y = v;
                }
            }
            for(auto a : e[u])for(auto b : e[u])if(vis[a] && vis[b] && a!=b){
                int w = max({W(a,u),W(b,u),all - W(a,u) - W(b,u)});
                if(rw > w){
                    rw = w; x = a,y = b;
                }
            }
        }
        //
        dep[x] = fa[x] = 0; dfs(x); for(int i=1;i<=n;i++)dx[i] = dep[i];
        dep[y] = fa[y] = 0; dfs(y); for(int i=1;i<=n;i++)dy[i] = dep[i];
        printf("? %d %d\n",x,y); fflush(stdout);
        int res; scanf("%d",&res);
        for(int i=1;i<=n;i++)if(vis[i]){
            if(res == 0)vis[i] = (dx[i] < dy[i]);
            else if(res == 1)vis[i] = (dx[i] == dy[i]);
            else vis[i] = (dx[i] > dy[i]);
        }
    }
}

int main(){
    scanf("%d",&T);
    while(T--)solve();

    return 0;
}