#include <bits/stdc++.h>

using namespace std;

#define int long long

// std::mt19937_64 mrand(std::chrono::steady_clock().now().time_since_epoch().count());
std::mt19937_64 mrand(0);
int rnd(int l, int r) {
    return mrand() % (r - l + 1) + l;
}

struct Interactor {
    int n, s;
    std::queue<int> in;
    std::vector<int> dis;
    Interactor() {
        n = rnd(2, 7);
        s = rnd(1, n);
        in.push(n);
        dis.assign(n + 1, 1E18);

        std::vector<std::vector<int>> adj(n + 1), son(n + 1);
        std::vector<int> d(n + 1);

        for (int i = 2; i <= n; i++) {
            int x = rnd(1, i - 1);
            while (d[x] >= 2) {
                x = rnd(1, i - 1);
            }
            adj[x].push_back(i);
            adj[i].push_back(x);
            son[x].push_back(i);
            d[x]++;
        }

        std::cout << "!!!" << n << " " << s << std::endl;
        for (int i = 1; i <= n; i++) {
            int x = 0, y = 0;
            if (son[i].size() >= 1) {
                x = son[i][0];
            }
            if (son[i].size() >= 2) {
                y = son[i][1];
            }

            in.push(x);
            in.push(y);
            std::cerr << x << " " << y << std::endl;
        }

        dis[s] = 0;
        std::queue<int> q;
        q.push(s);
        while (q.size()) {
            auto x = q.front();
            q.pop();
            for (auto y : adj[x]) {
                if (dis[y] > dis[x] + 1) {
                    dis[y] = dis[x] + 1;
                    q.push(y);

                }
            }
        }
    }
    int read() {
        int x = in.front();
        in.pop();
        return x;
    }

    int query(int u, int v) {
        std::cerr << "query " << u << " " << v << " " << dis[u] << " " << dis[v] << std::endl;
        if (dis[u] < dis[v]) {
            return 0;
        } else if (dis[u] > dis[v]) {
            return 2;
        } else {
            return 1;
        }
    }

    void answer(int x) {
        assert(x == s);
    }

    // int query(int u, int v) {
    //     tot--;
    //     assert(tot >= 0);
    //     std::cout << "? " << u << " " << v << std::endl;
    //     int x;
    //     std::cin >> x;
    //     return x;
    // }

    // int read() {
    //     int x;
    //     std::cin >> x;
    //     return x;
    // }
    // void answer(int x) {
    //     std::cout << "! " << x << std::endl;
    // }
};


int tot = 0;



void solve() {
    Interactor it;
    int n;
    n = it.read();
    tot = std::__lg(n);
    std::vector<std::vector<int>> adj(n + 1);
    for (int i = 1; i <= n; i++) {
        int ls, rs;
        ls = it.read();
        rs = it.read();
        if (ls) {
            adj[i].push_back(ls);
            adj[ls].push_back(i);
        }
        if (rs) {
            adj[i].push_back(rs);
            adj[rs].push_back(i);
        }
    }

    std::vector<int> vis(n + 1), sz(n + 1), f(n + 1);
    f[0] = 1E9;
    auto work = [&](auto self, int x, int SZ) -> void {
        if (SZ == 1) {
            it.answer(x);
            return;
        }
        auto p = 0;
        auto dfs = [&](auto self, int x, int fx) -> void {
            sz[x] = 1;
            f[x] = 0;
            for (auto y : adj[x]) {
                if (y == fx || vis[y] == 1) continue;
                self(self, y, x);
                sz[x] += sz[y];
                f[x] = std::max(f[x], sz[y]);
            }
            f[x] = std::max(f[x], SZ - sz[x]);
            if (f[x] < f[p]) {
                p = x;
            }

        };
        dfs(dfs, x, 0);
        dfs(dfs, p, 0);

        // std::cerr << "!!!" << p << std::endl;
        std::vector<int> vec;
        for (auto y : adj[p]) {
            if (vis[y] == 0) {
                vec.push_back(y);
            }
        }
        if (vec.size() == 1) {
            int a = p, b = vec[0];
            int v = it.query(a, b);
            if (v == 0) {
                it.answer(a);
            } else if (v == 2) {
                it.answer(b);
            } else {
                assert(0);
            }
        } else if (vec.size() == 2) {
            int a = vec[0], b = vec[1];
            int v = it.query(a, b);
            vis[p] = 1;
            if (v == 0) {
                self(self, a, sz[a]);
            } else if (v == 2) {
                self(self, b, sz[b]);
            } else {
                it.answer(p);
            }
        } else if (vec.size() == 3) {
            int a = vec[0], b = vec[1];
            int v = it.query(a, b);

            if (v == 0) {
                self(self, a, sz[a]);
            } else if (v == 2) {
                self(self, b, sz[b]);
            } else {
                vis[a] = vis[b] = 1;
                self(self, vec[2], sz[vec[2]] + 1);
            }
        }

    };
    work(work, 1, n);
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int t = 1;
    std::cin >> t;

    while (t --) {
        solve();
    }
}


PS C:\Users\G\Desktop\Nanjing> cd "c:\Users\G\Desktop\Nanjing\" ; if ($?) { g++ G.cpp -o G } ; if ($?) { .\G }
5
!!!2 2
2 0
0 0
query 2 1 0 1
!!!2 1
2 0
0 0
query 2 1 1 0
!!!3 1
2 0
3 0
0 0
query 1 3 0 2
!!!7 2
2 3
4 5
6 0
0 0
0 0
7 0
0 0
query 2 3 0 2
query 4 5 1 1
!!!7 4
2 4
3 7
5 6
0 0
0 0
0 0
0 0
query 1 3 1 3
query 5 3 4 3
Assertion failed: x == s, file G.cpp, line 85
PS C:\Users\G\Desktop\Nanjing> 

answer.code:217:6: error: stray ‘\’ in program
  217 | PS C:\Users\G\Desktop\Nanjing> cd "c:\Users\G\Desktop\Nanjing\" ; if ($?) { g++ G.cpp -o G } ; if ($?) { .\G }
      |      ^
answer.code:217:12: error: stray ‘\’ in program
  217 | PS C:\Users\G\Desktop\Nanjing> cd "c:\Users\G\Desktop\Nanjing\" ; if ($?) { g++ G.cpp -o G } ; if ($?) { .\G }
      |            ^
answer.code:217:14: error: stray ‘\’ in program
  217 | PS C:\Users\G\Desktop\Nanjing> cd "c:\Users\G\Desktop\Nanjing\" ; if ($?) { g++ G.cpp -o G } ; if ($?) { .\G }
      |              ^
answer.code:217:22: error: stray ‘\’ in program
  217 | PS C:\Users\G\Desktop\Nanjing> cd "c:\Users\G\Desktop\Nanjing\" ; if ($?) { g++ G.cpp -o G } ; if ($?) { .\G }
      |                      ^
answer.code:217:35: warning: missing terminating " character
  217 | PS C:\Users\G\Desktop\Nanjing> cd "c:\Users\G\Desktop\Nanjing\" ; if ($?) { g++ G.cpp -o G } ; if ($?) { .\G }
      |                                   ^
answer.code:217:35: error: missing terminating " character
  217 | PS C:\Users\G\Desktop\Nanjing> cd "c:\Users\G\Desktop\Nanjing\" ; if ($?) { g++ G.cpp -o G } ; if ($?) { .\G }
      |                                   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:253:6: error: stray ‘\’ in program
  253 | PS C:\Users\G\Desktop\Nanjing>
      |      ^
answer.code:253:12: error: stray ‘\’ in program
  253 | PS C:\Users\G\Desktop\Nanjing>
      |            ^
answer.code:253:14: error: stray ‘\’ in program
  253 | PS C:\Users\G\Desktop\Nanjing>
      |              ^
answer.code:253:22: error: stray ‘\’ in program
  253 | PS C:\Users\G\Desktop\Nanjing>
      |                      ^
answer.code:217:1: error: ‘PS’ does not name a type
  217 | PS C:\Users\G\Desktop\Nanjing> cd "c:\Users\G\Desktop\Nanjing\" ; if ($?) { g++ G.cpp -o G } ; if ($?) { .\G }
      | ^~