#include <bits/stdc++.h>
// #define endl '\n'
#define int long long
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int query(int u, int v)
{
    fflush(stdout);
    cout << "? " << u << " " << v << endl;
    int x;
    cin >> x;
    return x;
}
void solve()
{
    int n;
    cin >> n;
    vector<set<int>> e(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        if (x != 0)
        {
            e[i].insert(x);
            e[x].insert(i);
        }
        if (y != 0)
        {
            e[i].insert(y);
            e[y].insert(i);
        }
    }
    int duan1 = 1;

    auto find_mid = [&](int p) -> int
        {
            int minl = 1e18;
            int ans = p;
            int ans_p = p;
            vector<int> sz(n + 1, 0);
            vector<int> dp(n + 1, 0);
            int cnt = 0;
            vector<int> donee(n + 1, 0);
            auto dfs2 = [&](auto dfs2, int u) -> void
                {
                    cnt++;
                    for (auto pp : e[u])
                    {
                        if (donee[pp] == 1)
                            continue;
                        donee[pp] = 1;
                        dfs2(dfs2, pp);
                    }
                };
            donee[p] = 1;
            dfs2(dfs2, p);

            auto dfs = [&](auto dfs, int u, int fa) -> int
                {
                    vector<int> t;
                    int tt = cnt - 1;
                    int sum = 1;
                    for (auto pp : e[u]) // 链式前向星遍历
                    {
                        if (pp == fa)continue;
                        int now = dfs(dfs, pp, u);
                        t.push_back(now + 1);
                        tt -= now;
                        sum += now;
                    }
                    for (auto x : t)
                    {
                        if ((cnt % 2 == 0 && (x == cnt / 2 || x == cnt / 2 + 1)) || (cnt % 2 == 1 && x == cnt / 2 + 1)) ans = u;
                    }

                    return sum;
                };
            dfs(dfs, p, 0);
            return ans;
        };

    // cerr << find_mid(1) << endl;

    auto cont_size = [&](int p, int x) -> int
        {
            queue<int> qq;
            qq.push(p);
            vector<int> done(n + 1, 0);
            done[x] = 1;
            while (!qq.empty())
            {
                int pp = qq.front();
                qq.pop();
                done[pp] = 1;
                for (auto nxt : e[pp])
                {
                    if (done[nxt] == 0)
                        qq.push(nxt);
                }
            }

            int cnt = 0;
            for (int i = 1; i <= n; i++)
            {
                cnt += done[i];
            }
            return cnt;
        };

    while (1)
    {
        int p_mid = find_mid(duan1);
        // cerr << "________________" << endl;
        // for (auto ppp : e[2])
        //{
        //     cout << ppp << " ";
        // }
        // cerr << endl<<endl;
        //cerr << "_____  " << p_mid << " " << duan1 << endl;
        if (e[p_mid].size() == 0)
        {
            cout << "! " << p_mid << endl;
            return;
        }
        else if (e[p_mid].size() == 1)
        {
            vector<int> lin;
            for (auto p : e[p_mid])
            {
                lin.push_back(p);
            }
            if (query(p_mid, lin[0]) == 0)
                cout << "! " << p_mid << endl;
            else
                cout << "! " << lin[0] << endl;
            return;
        }
        else if (e[p_mid].size() == 2)
        {
            vector<int> lin;
            for (auto p : e[p_mid])
            {
                lin.push_back(p);
            }

            int op = query(lin[0], lin[1]);
            if (op == 0)
            {
                e[p_mid].erase(lin[0]);
                e[lin[0]].erase(p_mid);
                duan1 = lin[0];
            }
            else if (op == 1)
            {
                cout << "! " << p_mid << endl;
                return;
            }
            else if (op == 2)
            {
                e[p_mid].erase(lin[1]);
                e[lin[1]].erase(p_mid);
                duan1 = lin[1];
            }
        }
        else if (e[p_mid].size() == 3)
        {
            vector<int> lin;
            for (auto p : e[p_mid])
            {
                lin.push_back(p);
            }

            vector<int> cnt_lin(3);
            for (int i = 0; i < 3; i++)
            {
                cnt_lin[i] = cont_size(lin[i], p_mid);
            }

            int mmin = cnt_lin[0];
            int p_mmin = 0;
            for (int i = 0; i < 3; i++)
            {
                if (cnt_lin[i] < mmin)
                {
                    mmin = cnt_lin[i];
                    p_mmin = i;
                }
            }

            int a, b;
            if (p_mmin == 0)
            {
                a = lin[1];
                b = lin[2];
            }
            else if (p_mmin == 1)
            {
                a = lin[0];
                b = lin[2];
            }
            else if (p_mmin == 2)
            {
                a = lin[1];
                b = lin[0];
            }

            int op = query(a, b);
            if (op == 0)
            {
                e[p_mid].erase(a);
                e[a].erase(p_mid);
                duan1 = a;
            }
            else if (op == 1)
            {
                e[p_mid].erase(a);
                e[a].erase(p_mid);
                e[p_mid].erase(b);
                e[b].erase(p_mid);
                duan1 = p_mid;
            }
            else if (op == 2)
            {
                e[p_mid].erase(b);
                e[b].erase(p_mid);
                duan1 = b;
            }
        }
    }
    // for (int i=1;i<=n;i++)
    // {
    //     cerr<<i<<" "<<e[i].size()<<endl;
    // }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

/*


8
2 0
8 6
0 0
3 0
0 0
7 0
0 0
5 4






8
0 0
1 4
2 0
0 0
7 8
0 0
3 0
6 0



8
5 8
0 0
1 7
0 0
0 0
4 2
0 0
6 0


*/