#include<bits/stdc++.h> 
using namespace std;
struct node{
	int next,number;
}a[100005];
int b[100005];
int main(){
	a[1].number=1;
	a[1].next=0;
	b[1]=1;
	int p;
	cin>>p;
	int cnt=1;
	while(p--){
		int o;
		cin>>o;
		if(o==1){
			int x,y;
			cin>>x>>y;
			cnt++;
			b[y]=cnt;
			a[b[y]].next=a[b[x]].next;
			a[b[x]].next=b[y];
			a[b[y]].number=y;
		}
		if(o==2){
			int x;
			cin>>x;
			if(b[x]==cnt){cout<<0<<"\n";continue;}
			cout<<a[a[b[x]].next].number<<"\n";
		}
		if(o==3){
			int x;
			cin>>x;
			a[b[x]].next=a[a[b[x]].next].next;
			cnt--;
		}
	}
	return 0;
}