#include<bits/stdc++.h>
using namespace std;
using ll = long long;

struct node{
    int to;
    int id;
};

void solve(){
    int n;
    cin >> n;
    vector<vector<node>> e(n + 1);
    int times = 0;
    vector<int> vi(n * 5);
    for(int i = 1; i <= n; i++){
        int a, b;
        cin >> a >> b;
        if(a != 0){
            e[a].push_back({i, ++times});
            e[i].push_back({a, times});
            vi[times] = 1;
        }
        if(b != 0){
            e[i].push_back({b, ++times});
            e[b].push_back({i, times});
            vi[times] = 1;
        }
    }
    auto getsize = [&](auto&& getsize, int u, int f) -> int {
        int x = 1;
        for(auto [v, id] : e[u]){
            if(v == f)continue;
            if(vi[id] == 0)continue;
            x += getsize(getsize, v, u);
        }
        return x;
    };
    auto find = [&](int x) -> int {
        vector<int> fa(n + 1);
        vector<int> ans(n + 1);
        vector<int> siz(n + 1);
        vector<int> big(n + 1);
        auto dfs = [&](auto&& dfs, int u) -> void {
            // cout << u << endl;
            siz[u] = 1;
            ans[u] = u;
            for(auto [v, id] : e[u]){
                if(vi[id] == 0)continue;
                if(fa[u] == v){continue;}
                fa[v] = u;
                dfs(dfs, v);
                siz[u] += siz[v];
                big[u] = max(big[u], siz[v]);
            }
            for(auto [v, id] : e[u]){
                if(vi[id] == 0)continue;
                if(fa[u] == v){continue;}
                int p = ans[v];
                while(p != u){
                    if(max(big[p], siz[u] - siz[p]) <= siz[u] / 2){
                        ans[u] = p;
                        break;
                    }else{
                        p = fa[p];
                    }
                }
            }
        };
        fa[x] = x;
        dfs(dfs, x);
        return ans[x];
    };
    auto work = [&](auto&& work, int u) -> void {
        // cout << "aaaaa" << endl;
        u = find(u);
        int cnt = 0;
        vector<node> temp;
        for(auto [v, id] : e[u]){
            if(vi[id]){cnt++; temp.push_back({v, id});}
        }
        if(cnt == 0){cout << "! " << u << endl;}
        else if(cnt == 1){
            int f = temp[0].to;
            cout << "? " << f << " " << u << endl;
            int op;
            cin >> op;
            if(op == 0){cout << "! " << f << endl;return ;}
            else if(op == 2){cout << "! " << u << endl; return ;}
        }
        else if(cnt == 2){
            int f = temp[0].to;
            int v = temp[1].to;
            cout << "? " << f << " " << v << endl;
            int op;
            cin >> op;
            if(op == 1){
                cout << "! " << u << endl;
                return ;
            }
            else if(op == 0){
                vi[temp[0].id] = 0;
                work(work, f);
            }
            else if(op == 2){
                vi[temp[1].id] = 0;
                work(work, v);
            }
        }
        else if(cnt == 3){
            vector<pair<int, pair<int, int>>> tt;
            for(auto [v, id] : e[u]){
                tt.push_back({getsize(getsize, v, u), {v, id}});
            } 
            // sort(tt.begin(), tt.end());
            int f = tt[2].second.first;
            int v = tt[1].second.first;
            cout << "? " << f << " " << v << endl;
            int op;
            cin >> op;
            if(op == 1){
                vi[tt[1].second.second] = 0;
                vi[tt[2].second.second] = 0;
                work(work, u);
            }
            else if(op == 0){
                vi[tt[2].second.second] = 0;
                work(work, f);
            }
            else if(op == 2){
                vi[tt[1].second.second] = 0;
                work(work, v);
            }
        }
    };
    work(work, 1);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    solve();
    return 0;
}