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

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

    vector<int> siz(n + 1), ans;
    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)
        {
            g[i].insert(l);
            g[l].insert(i);
            st.erase(l);
        }
        if (r)
        {
            g[i].insert(r);
            g[r].insert(i);
            st.erase(r);
        }
    }

    int maxnum = 1e9;
    auto dfs = [&](auto dfs, int u, int fa) -> void
    {
        siz[u] = 1;
        int tmp = 0;
        for (auto v : g[u])
        {
            if (v == fa)
                continue;
            dfs(dfs, v, u);

            siz[u] += siz[v];
            tmp = max(tmp, siz[v]);
        }

        tmp = max(tmp, n - siz[u]);

        if (tmp < maxnum)
        {
            maxnum = tmp;
            ans.clear();
            ans.push_back(u);
        }
    };

    dfs(dfs, 1, 0);
    int root = *ans.begin();
    dfs(dfs, root, 0);

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

    // cout << root << endl;
    // 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;
}