#include <bits/stdc++.h>
using namespace std;
#define pii pair<int , int>
const int mod = 1e9 + 7 ;

vector<vector<int>>adjList ;
vector<vector<int>>up ;
void build(int source , int parent){
    up[source][0] = parent ;
    for(int i = 1 ; i < 20 ; i++){
        if(up[source][i-1] == -1){
            up[source][i] = -1 ;
        }
        else{
            up[source][i] = up[up[source][i-1]][i-1];
        }
    }

    for(auto it : adjList[source]){
        if(it != parent){
            build(it , source);
        }
    }
}
int query(int node , int k){
    if(node == -1 || k == 0)
        return node ;
    for(int i = 19 ; i >= 0 ; i--){
        if(k >= (1<<i)){
            return query(up[node][i] , k - (1<<i));
        }
    }
    return -1 ;
}
void store(int node , int parent){
    up[node][0] = parent ;
    for(int i = 1 ; i < 20 ; i++){
        if(up[node][i-1] == -1){
            up[node][i] = -1 ;
        }
        else{
            up[node][i] = up[up[node][i-1]][i-1];
        }
    }
}
void remove(int node ){
    for(int i = 0 ; i < 20 ; i++){
        up[node][i] = -1 ;
    }
}
void solve(){
    up = vector<vector<int>>(200005 , vector<int>(20, -1));
    int n;
    cin>>n;
    adjList.resize(200005 );
    int root = - 1 ;
    for(int i = 0 ; i < n ; i++){
        int x, y ;
        cin>>x>>y;
        --x , --y ;
        if(y == -1){
            root = x ;
        }
        else{
            adjList[x].push_back(y);
            adjList[y].push_back(x);
        }
    }
    build(root , -1);
    int q ;
    cin>>q;
    for(int i = 0 ; i < q ; i++){
        int type ;
        cin>>type;
        if(type == 0){
            int y , x ;
            cin>>y>>x;
            --x , -- y ;
            store(x , y);
        }
        else if(type == 1){
            int x;
            cin>>x;
            --x;
            remove(x);
        }
        else{
            int x , k ;
            cin>>x>>k;
            --x;
            cout<<query(x , k) + 1<<endl;
        }

    }
}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}