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

void solve()
{
    int n;
    cin >> n;

    vector<int> fa(n + 1), siz(n + 1), ans(n + 1), weight(n + 1);
    vector<set<int>> g(n + 10, set<int>());

    set<int> st;
    for (int i = 1; i <= n; i++)
        st.insert(i);

    for (int i = 1; i <= n; i++)
    {
        int l, r;
        cin >> l >> r;
        if (l)
        {
            fa[l] = i;
            g[i].insert(l);
            g[l].insert(i);
            st.erase(l);
        }
        if (r)
        {
            fa[r] = i;
            g[i].insert(r);
            g[r].insert(i);
            st.erase(r);
        }
    }

    auto dfs = [&](auto dfs, int u) -> void
    {
        siz[u] = 1, ans[u] = u;
        for (int v : g[u])
        {
            if (v == fa[u])
                continue;
            dfs(dfs, v);
            siz[u] += siz[v];
            weight[u] = max(weight[u], siz[v]);
        }
        for (int v : g[u])
        {
            if (v == fa[u])
                continue;
            int p = ans[v];
            while (p != u)
            {
                if (max(weight[p], siz[u] - siz[p]) <= siz[u] / 2)
                {
                    ans[u] = p;
                    break;
                }
                else
                    p = fa[p];
            }
        }
    };

    int root = *st.begin();

    dfs(dfs, root);
    root = ans[root];

    auto dfs2 = [&](auto dfs2, int u) -> void
    {
        siz[u] = 1, ans[u] = u;
        for (int v : g[u])
        {
            if (v == fa[u])
                continue;
            dfs2(dfs2, v);
            siz[u] += siz[v];
            weight[u] = max(weight[u], siz[v]);
        }
    };

    dfs2(dfs2, root);

    int u = root, v = *g[root].begin();
    for (auto tmp : g[u])
    {
        if (siz[tmp] > siz[v])
            v = tmp;
    }

    // for (int i = 1; i <= n; i++)
    //     cout << g[i].size() << ' ';
    // cout << endl;

    int father = -1, flag = false;
    while (1)
    {
        cout << "? " << u << ' ' << v << '\n';
        fflush(stdout);

        int t;
        cin >> t;
        if (t == 0)
        {
            if (flag)
            {
                v = father;
            }
            g[u].erase(v);
            g[v].erase(u);

            if (g[u].size() == 2)
            {
                father = u;
                v = *g[u].rbegin();
                u = *g[u].begin();
                flag = true;
            }
            else if (g[u].size() == 1)
            {
                v = *g[u].begin();
                flag = false;
            }
            else
            {
                cout << "! " << u << '\n';
                fflush(stdout);
                return;
            }
        }
        else if (t == 1)
        {
            cout << "! " << father << '\n';
            fflush(stdout);
            return;
        }
        else if (t == 2)
        {
            swap(u, v);
            if (flag)
            {
                v = father;
            }
            g[u].erase(v);
            g[v].erase(u);

            if (g[u].size() == 2)
            {
                father = u;
                v = *g[u].rbegin();
                u = *g[u].begin();
                flag = true;
            }
            else if (g[u].size() == 1)
            {
                v = *g[u].begin();
                flag = false;
            }
            else
            {
                cout << "! " << u << '\n';
                fflush(stdout);
                return;
            }
        }
    }
}

int main()
{
    // cin.tie(0)->ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}