//关注不变量
//多次查询可以思考根号分治
//位运算有关多想拆位
//字符串多想hash
//对字符串频繁操作可以映射成整数
//点的限制加到边上
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef __int128 i128;
const int INF = 0x3f3f3f3f;
const int N = 4e5 + 10, mod = 1e9 + 7;

void solve() {
    int n;
    cin >> n;
    vector<set<int>> g(n + 1);  //存图
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        if (x) {
            g[x].insert(i);
            g[i].insert(x);
        }
        if (y) {
            g[y].insert(i);
            g[i].insert(y);
        }
    }

    vector<int> sz(n + 1, 0), father(n + 1, 0); //每个点子树的sz，和父亲
    int root = 1;
    auto get_sz = [&](auto get_sz, int u, int fa) -> void { //搜sz
        sz[u] = 1;
        father[u] = fa;
        for (auto v : g[u]) {
            if (v == fa) continue;
            get_sz(get_sz, v, u);
            sz[u] += sz[v];
        }
    };
    int aim = root, aimval = 1e8;  //重心
    auto get_mid = [&](auto get_mid, int u, int fa) -> void { //求重心
        int mx = 0;
        for (auto v : g[u]) {
            if (v == fa) continue;
            get_mid(get_mid, v, u);
            mx = max(mx, sz[v]);
        }
        mx = max(sz[root] - sz[u], mx);
        if (mx < aimval) {
            aim = u;
            aimval = mx;
        }
    };

    int tot = 0;
    auto query = [&](int u, int v) -> int {
        tot++;
        if((1ll << tot) <= n) {
            cout << "WAA\n";
            return ;
        }
        assert((1ll << tot) <= n);
        cout << "? " << u << ' ' << v << endl;
        int res;
        cin >> res;
        return res;
    };

    while (1) {
        get_sz(get_sz, root, 0);
        aim = root, aimval = 1e8;
        get_mid(get_mid, root, 0);
        if (g[aim].size() == 0) {   //一个点
            cout << "! " << aim << endl;
            return;
        }
        else if (g[aim].size() == 1) { //全图只有两个点
            int u;
            for (auto v : g[aim]) u = v;
            auto res = query(aim, u);
            if (res == 0) cout << "! " << aim << endl;
            else cout << "! " << u << endl;
            return;
        }
        else if (g[aim].size() == 2) { //询问两边的点
            int u, v;
            int num = 0;
            for (auto k : g[aim]) {
                if (!num) u = k;
                else v = k;
                num++;
            }
            auto res = query(u, v);
            if (res == 0) {
                g[u].erase(aim);
                g[aim].erase(u);
                root = u;
            }
            else if (res == 1) {
                cout << "! " << aim << endl;
                return;
            }
            else {
                g[v].erase(aim);
                g[aim].erase(v);
                root = v;
            }
        }
        else {  //询问最大的两个邻居上的点
            int aim1 = 0, aim2 = 0, num = 0;
            for (auto v : g[aim]) {
                if (v == father[aim]) continue;
                num++;
                if (num == 1) aim1 = v;  //第一个邻居
                else aim2 = v; //第二个邻居
            }
            int fa = father[aim]; //父亲
            vector<PII> s(3);
            s[0] = {sz[aim1], aim1};
            s[1] = {sz[aim2], aim2};
            s[2] = {sz[root] - sz[aim], fa};
            sort(s.begin(), s.end(), [&](PII a, PII b) {
                return a.first > b.first;
            });
            int u = s[0].second, v = s[1].second;
            auto res = query(u, v);
            if (res == 0) {
                g[u].erase(aim);
                g[aim].erase(u);
                root = u;
            }
            else if (res == 1) {
                g[aim].erase(u);
                g[u].erase(aim);
                g[aim].erase(v);
                g[v].erase(aim);
                root = aim;
            }   
            else {
                g[v].erase(aim);
                g[aim].erase(v);
                root = v;
            }
        }
    }
}

signed main() {
    // ios::sync_with_stdio(false);
    // cin.tie(0);
    // cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) solve();
    return 0;
}

answer.code: In lambda function:
answer.code:65:13: error: return-statement with no value, in function returning ‘int’ [-fpermissive]
   65 |             return ;
      |             ^~~~~~