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

void RES(int x) {
    cout << "! " << x << endl;
}

void ASK(int u, int v) {
    cout << "? " << u << " " << v << endl;
}

int GET() {
    int op; cin >> op;
    return op;
}

void solve1() {
    int n; cin >> n;
    vector<vector<int>> G(n + 1);
    for (int i = 1;i <= n;i++) {
        int a, b; cin >> a >> b;
        if (a) {
            G[a].push_back(i);
            G[i].push_back(a);
        }
        if (b) {
            G[b].push_back(i);
            G[i].push_back(b);
        }
    }

    auto removeit = [&](vector<int>& arr, int x) {
        int pos = -1;
        for (int i = 0;i < arr.size();i++) {
            if (arr[i] == x) {
                pos = i;
                break;
            }
        }
        if (pos != -1) {
            arr.erase(arr.begin() + pos);
        }
    };

    auto dfs = [&](auto&&dfs, int st, int ps) -> void {
        int m = 0;
        auto cnt = [&](auto&&cnt, int u, int fa) -> void {
            m++;
            for (int v : G[u]) {
                if (v == fa) continue;
                cnt(cnt, v, u);
            }
        };
        cnt(cnt, st, ps);

        // cout << "m: " << m << endl;

        vector<int> sz(n + 1, 0), w(n + 1, 0), centroid(2, 0);
        auto getCentroid = [&](auto&&getCentroid, int u, int fa) -> void {
            sz[u] = 1;
            w[u] = 0;
            for (int v : G[u]) {
                if (v == fa) continue;
                getCentroid(getCentroid, v, u);
                sz[u] += sz[v];
                w[u] = max(w[u], sz[v]);
            }
            w[u] = max(w[u], m - sz[u]);
            // cout << u << ": " << w[u] << endl;
            if (w[u] <= m / 2) centroid[centroid[0] != 0] = u;
        };
        getCentroid(getCentroid, st, ps);
        int root = centroid[0];
        if (G[root].size() == 1 && centroid[1] != 0) {
            root = centroid[1];
        }
        sz.assign(n + 1, 0);
        auto getSize = [&](auto&&getSize, int u, int fa) -> void {
            sz[u] = 1;
            for (int v : G[u]) {
                if (v == fa) continue;
                getSize(getSize, v, u);
                sz[u] += sz[v];
            }
        };
        getSize(getSize, root, root);
        // cout << "root: " << root << " " << G[root].size() << endl;
        auto& son = G[root];
        if (son.size() == 0) {
            RES(root);
            return;
        }
        else if (son.size() == 1) {
            ASK(root, son[0]);
            int op = GET();
            if (op == 0) RES(root);
            else RES(son[0]);
            return;
        }
        else if (son.size() == 2) {
            int lson = son[0], rson = son[1];
            removeit(G[lson], root);
            removeit(G[rson], root);
            // remove(G[lson].begin(), G[lson].end(), root);
            // remove(G[rson].begin(), G[rson].end(), root);
            G[root].clear();
            ASK(lson, rson);
            int op = GET();
            if (op == 1) {
                RES(root);
                return;
            }
            else if (op == 0) dfs(dfs, lson, root);
            else dfs(dfs, rson, root);
        }
        else if (son.size() == 3) {
            sort(son.begin(), son.end(), [&](int x, int y) {
                return sz[x] > sz[y];
            });
            int lson = son[0], rson = son[1], tson = son[2];

            removeit(G[lson], root);
            removeit(G[rson], root);
            // remove(G[lson].begin(), G[lson].end(), root);
            // remove(G[rson].begin(), G[rson].end(), root);
            G[root].clear();
            G[root].push_back(tson);
            ASK(lson, rson);
            int op = GET();
            if (op == 1) {
                dfs(dfs, root, root);
            }
            else if (op == 0) dfs(dfs, lson, root);
            else dfs(dfs, rson, root);
        }
    };
    dfs(dfs, 1, 1);
}

void solve() {
    int n; cin >> n;
    vector<vector<int>> G(n + 1);
    for (int i = 1;i <= n;i++) {
        int a, b; cin >> a >> b;
        if (a) {
            G[a].push_back(i);
            G[i].push_back(a);
        }
        if (b) {
            G[b].push_back(i);
            G[i].push_back(b);
        }
    }

    auto removex = [&](vector<int>& arr, int x) {
        int pos = -1;
        for (int i = 0;i < arr.size();i++) {
            if (arr[i] == x) {
                pos = i; break;
            }
        }
        if (pos != -1) arr.erase(arr.begin() + pos);
    };

    int ok = 0;
    auto dfs = [&](auto&&dfs, int u, int fa) -> void {
        if (ok) return;
        if (G[u].size() == 0) {
            RES(u);
            ok = 1;
            return;
        }
        else if (G[u].size() == 1) {
            int v = G[u][0];
            ASK(u, v);
            int op = GET();
            if (op == 0) {
                RES(u);
                ok = 1;
                return;
            }
            removex(G[v], u);
            dfs(dfs, v, u);
        }
        else if (G[u].size() == 2) {
            int v1 = G[u][0], v2 = G[u][1];
            ASK(v1, v2);
            int op = GET();
            removex(G[u], v1);
            removex(G[u], v2);
            removex(G[v1], u);
            removex(G[v2], u);
            if (op == 1) {
                RES(u);
                ok = 1;
                return;
            }
            else if (op == 0) {
                dfs(dfs, v1, u);
            }
            else dfs(dfs, v2, u);
        }
        else {
            int v1 = G[u][0], v2 = G[u][1], v3 = G[u][2];
            removex(G[u], v1);
            removex(G[u], v2);
            removex(G[v1], u);
            removex(G[v2], u);
            ASK(v1, v2);
            int op = GET();
            if (op == 1) {
                dfs(dfs, v3, u);
            }
            else if (op == 0) {
                dfs(dfs, v1, u);
            }
            else dfs(dfs, v2, u);
        }
    };
    dfs(dfs, 1, 1);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for (int i = 0;i < t;i++) {
        if (i < 2) solve1();
        else solve();
    }
    // while (t--) solve();
    return 0;
}