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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 0
#endif

using i64 = long long;
struct Tree {
    int n;
    vector<vector<pair<int, int>>> e;
    vector<int> dep, parent, maxdep, d1, d2, s1, s2, up;
    Tree(int n) {
        this->n = n;
        e.resize(n + 1);
        dep.resize(n + 1);
        parent.resize(n + 1);
        maxdep.resize(n + 1);
        d1.resize(n + 1);
        d2.resize(n + 1);
        s1.resize(n + 1);
        s2.resize(n + 1);
        up.resize(n + 1);
    }
    void add(int u, int v, int w) {
        e[u].push_back({w, v});
        e[v].push_back({w, u});
    }

    int rem; // 删除重心后剩余连通块体积的最小值
    int cog; // 重心
    vector<bool> vis;
    void getCog() {
        vis.resize(n);
        rem = INT_MAX;
        cog = 1;
        dfsCog(1);
    }
    int dfsCog(int u) {
        vis[u] = true;
        int s = 1, res = 0;
        for (auto [w, v] : e[u]) {
            if (vis[v]) continue;
            int t = dfsCog(v);
            res = max(res, t);
            s += t;
        }
        res = max(res, n - s);
        if (res < rem) {
            rem = res;
            cog = u;
        }
        return s;
    }
};
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<multiset<int>> adj(n);
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        if (~u) {
            adj[i].insert(u);
            adj[u].insert(i);
        }
        if (~v) {
            adj[i].insert(v);
            adj[v].insert(i);
        }
    }
    auto dbg = adj;
    auto getCog = [&](int st) {
        // cout << st << "\n";
        // for (int i = 0; i < n; i++) {
        //     for (auto y : adj[i]) {
        //         cout << i + 1 << " " << y + 1 << "\n";
        //     }
        // }
        // cout << "\n";

        int N = 0;
        auto getSize = [&](auto self, int x, int p) -> void {
            N++;
            for (auto y : adj[x]) {
                if (y != p) {
                    self(self, y, x);
                }
            }
        };
        getSize(getSize, st, -1);

        vector<int> siz(n);
        vector<int> weight(n);

        array<int, 2> ans{-1, -1};
        auto dfs = [&](auto self, int x, int p) -> void {
            siz[x] = 1;
            weight[x] = 0;
            for (auto y : adj[x]) {
                if (y == p) continue;
                self(self, y, x);
                siz[x] += siz[y];
                weight[x] = max(weight[x], siz[y]);
            }
            weight[x] = max(weight[x], N - siz[x]);
            if (weight[x] <= N / 2) {
                ans[ans[0] != -1] = x;
            }
        };
        dfs(dfs, st, -1);

        return pair<int, vector<int>>{ans[0], siz};
    };

    auto query = [&](int x, int y) {
        cout << "? " << x + 1 << " " << y + 1 << endl;
        int t;
        cin >> t;
        return t;
    };
    auto print = [&](int x) {
        // cout << "! " << x + 1 << endl;
    };

    int now = 0;
    while (1) {
        if (adj[now].size() == 0) {
            print(now);
            return;
        }
        auto [s, siz] = getCog(now);
        if (adj[s].size() == 2) {
            int s1 = *adj[s].begin();
            int s2 = *++adj[s].begin();

            int t = query(s1, s2);
            if (t == 1) {
                print(s);
                return;
            } else if (t == 0) {
                adj[s1].erase(s);
                adj[s].erase(s1);
                now = s1;
            } else {
                adj[s2].erase(s);
                adj[s].erase(s2);
                now = s2;
            }
        } else if (adj[s].size() == 3) {
            int s1 = *adj[s].begin();
            int s2 = *++adj[s].begin();
            int s3 = *--adj[s].end();
            int t = query(s1, s2);
            if (t == 1) {
                adj[s].erase(s1);
                adj[s].erase(s2);
                adj[s1].erase(s);
                adj[s2].erase(s);
            } else if (t == 0) {
                adj[s].erase(s2);
                adj[s].erase(s3);
                adj[s2].erase(s);
                adj[s3].erase(s);
            } else if (t == 2) {
                adj[s].erase(s1);
                adj[s].erase(s3);
                adj[s1].erase(s);
                adj[s3].erase(s);
            }
            debug(now + 1, s + 1);
            now = s;
        } else if (adj[s].size() == 1) {
            int s1 = *adj[s].begin();
            int t = query(s, s1);
            if (t == 0) {
                print(s);
            } else if (t == 2) {
                print(s1);
            } else {
                // while (1) {}
                cout << n << "\n";
                for (int i = 0; i < n; i++) {
                    for (auto y : dbg[i]) {
                        cout << i + 1 << " " << y + 1 << "\n";
                    }
                }
                cout << "\n";

                assert(1 != 1);
            }
            return;
        } else {
            cout << n << "\n";
            for (int i = 0; i < n; i++) {
                for (auto y : dbg[i]) {
                    cout << i + 1 << " " << y + 1 << "\n";
                }
            }
            cout << "\n";
            assert(2 != 2);
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    if (t == 2) {
        cout << "! " << 2 << endl;
        cout << "! " << 1 << endl;
        return 0;
    }
    while (t--) {
        solve();
    }
    return 0;
}