kth

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define ZERO (1e-10)
#define INF (1<<29)
#define CL(A,I) (memset(A,I,sizeof(A)))
#define DEB printf("DEB!\n");
#define D(X) cout<<"  "<<#X": "<<X<<endl;
#define EQ(A,B) (A+ZERO>B&&A-ZERO<B)
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
#define IN(n) int n;scanf("%d",&n);
#define FOR(i, m, n) for (int i(m); i < n; i++)
#define REP(i, n) FOR(i, 0, n)
#define F(n) REP(i, n)
#define FF(n) REP(j, n)
#define FT(m, n) FOR(k, m, n)
#define aa first
#define bb second
void ga(int N,int *A){F(N)scanf("%d",A+i);}
#define LS 18
#define MX (1<<LS)
vi g[MX];
int D[MX],P[MX][LS+1],N,E[MX],r;
void vnd(int u,int p,int d){
    P[u][0]=p,D[u]=d++;
    for(int i:g[u])if(i!=p)vnd(i,u,d);
}
void st(int r=1){
    vnd(r,r,0);
    F(LS)FF(MX-5)if(E[j+1])P[j+1][i+1]=P[P[j+1][i]][i];
}
int kth(int u,int K){
    int I(0);
    while(K){
        if(K&1)u=P[u][I];
        K>>=1,++I;
    }
    return u;
}
void tDB(int u,int p,int k){
    F(k)putchar(32);
    printf("%d [%d][%d]: S{",u,E[u],D[u]);
    for(auto h:g[u])if(h!=p)printf("%d,",h);
    printf("}: ");
    int I(1);
    F(LS)printf("(%d:%d) ",I,P[u][i]),I<<=1;
    putchar(10);
    for(auto h:g[u])if(h!=p)tDB(h,u,k+2);
}
int main(void){
    int a,b,q;
    IN(tt)F(tt){
//        DEB
        scanf("%d",&N);
        F(N){
            scanf("%d%d",&a,&b);
            if(!b)r=a;
            else g[a].PB(b),g[b].PB(a);
            E[b]=E[a]=1;
        }
        st(r);
        IN(Q)F(Q){
            scanf("%d",&q);
            if(q==2){
                //2 X K ... K-tý rodič X? - pokud X neexistuje nebo nema dost
                //rodicu, pak output == 0
                scanf("%d%d",&a,&b);
                if(!E[a]||D[a]<b){printf("0\n");continue;}
                printf("%d\n",kth(a,b));
//                tDB(r,-1,0);
            }else if(q){
                //1 X ... X je list k odstranění
                scanf("%d",&a);
                g[g[a][0]].erase(find(g[g[a][0]].begin(),g[g[a][0]].end(),a));
                E[a]=0,g[a].clear();
            }else{
                //0 Y X ... X je nový list Y
                scanf("%d%d",&a,&b);
                E[b]=1,g[b].PB(a),g[a].PB(b),D[b]=1+D[a],*P[b]=a;
                F(LS)P[b][i+1]=P[P[b][i]][i];
            }
        }
        CL(D,0),CL(P,0),CL(E,0);
        for(auto&v:g)v.clear();
    }
    return 0;
}