#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

int ask(int u, int v) {
    cout << "? " << u << " " << v << endl;
    int ret;
    cin >> ret;
    return ret;
}

void solve() {
    int n;
    cin >> n;
    
    vector<vector<pair<int, int>>> ver(n + 1);
    for (int i = 1; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        if (u) {
            ver[i].push_back({u, 1});
            ver[u].push_back({i, 1});
        }
        if (v) {
            ver[i].push_back({v, 1});
            ver[v].push_back({i, 1});
        }
    }
    
    int root = 1, MaxTree = 1e9; //分别代表重心下标、最大子树大小
    vector<int> vis(n + 1), siz(n + 1);
     auto get = [&](auto self, int x, int fa, int n) -> void { // 获取树的重心
        siz[x] = 1;
        int val = 0;
        for (auto [y, w] : ver[x]) {
            if (y == fa || vis[y] || w == 0) continue;
            self(self, y, x, n);
            siz[x] += siz[y];
            val = max(val, siz[y]);
        }
        val = max(val, n - siz[x]);
        if (val < MaxTree) {
            MaxTree = val;
            root = x;
        }
     };
     
    auto check = [&](int root, int fa) -> pair<bool, vector<int>> {
        vector<int> vec;
        vector<int> deg(n + 1);
        int a = -1;
        bool ok = true;
        function<void(int, int)> dfs = [&](int u, int fa) -> void {
            for (auto [v, T] : ver[u]) {
                if (v == fa || T == 0) {
                    continue;
                }
                deg[u]++;
                deg[v]++;
                dfs(v, u);
            }
            
            if (deg[u] >= 3) {
                ok = false;
            } else if (deg[u] == 1) {
                a = u;
            }
        };
        dfs(root, 0);
        if (!ok) {
            return {ok, vec};
        }
        // cerr << a << "ff\n";
        int p = -1;
        while (true) {
            vec.push_back(a);
            int gg = -1;
            for (auto [b, t] : ver[a]) {
                if (t == 0 || b == p) {
                    continue;
                }
                gg = b;
            }
            if (gg == -1) {
                break;
            }
            p = a;
            a = gg;
        }
        
        return {ok, vec};
    };
    
    while (true) {
        get(get, root, 0, n);
        
        auto [ok, vec] = check(root, 0);
        if (ok) {
            int lo = 0, hi = vec.size() - 1;
            while (lo < hi) {
                int sz = (hi - lo + 1) % 2;
                int mid = (lo + hi) / 2;
                int ret = ask(vec[lo], vec[hi]);
                if (ret == 0) {
                    if (sz & 1) {
                        hi = mid - 1;
                    } else {
                        hi = mid;
                    }
                } else if (ret == 1) {
                    assert(sz & 1);
                    if (sz & 1) {
                        cout << "! " << vec[mid] << endl;
                        return;
                    }
                } else {
                    if (sz & 1) {
                        lo = mid + 1;
                    } else {
                        lo = mid + 1;
                    }
                }
            }
            
            cout << "! " << vec[lo] << endl;
            return;
        }
        
        int a = -1, b = -1, c = -1;
        
        for (int i = 0; i < ver[root].size(); i++) {
            auto [_, T] = ver[root][i];
            if (T == 0) {
                continue;
            }
            if (a == -1) {
                a = i;
                continue;
            }
            if (b == -1) {
                b = i;
                continue;
            }
            if (c == -1) {
                c = i;
                continue;
            }
        }
        
        if ((~a) && (~b) && (~c)) {
            auto &[u, T1] = ver[root][a];
            auto &[v, T2] = ver[root][b];
            auto &[w, T3] = ver[root][c];
            // cerr << root << "f\n";
            // cerr  << u << " " << v << " " << w << "f\n";
            int ret = ask(u, v);
            
            T1 = 0;
            T2 = 0;
            for(auto &[x,t]:ver[u]){
                if(x==root){
                    t=0;
                }
            }
            for(auto &[x,t]:ver[v]){
                if(x==root){
                    t=0;
                }
            }
            
            if (ret == 0) {
                T3 = 0;
                for(auto &[x,t]:ver[w]){
                    if(x==root){
                        t=0;
                    }
                }
                root = u;
            } else if (ret == 1) {
            } else {
                T3 = 0;
                for(auto &[x,t]:ver[w]){
                    if(x==root){
                        t=0;
                    }
                }
                root = v;
            }
        } else if ((~a) && (~b)) {
            auto &[u, T1] = ver[root][a];
            auto &[v, T2] = ver[root][b];
            int ret = ask(u, v);
            T1 = 0;
            T2 = 0;
            for(auto &[x,t]:ver[u]){
                if(x==root){
                    t=0;
                }
            }
            for(auto &[x,t]:ver[v]){
                if(x==root){
                    t=0;
                }
            }
            
            if (ret == 0) {
                root = u;
            } else if (ret == 1) {
            } else {
                root = v;
            }
        } else if ((~a)){
            auto &[u, T] = ver[root][a];
            for(auto &[x,t]:ver[u]){
                if(x==root){
                    t=0;
                }
            }
            
            assert(a != -1);
            T = 0;
            int ret = ask(root, u);
            assert(ret != 1);
            if (ret == 2) {
                root = u;
            }
            cout << "! " << root << endl;
            return;
        } else {
            cout << "! " << root << endl;
            return;
        }
    }
}

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