#include <iostream> 
#include <cstdio> 
using namespace std;
struct node
{
	
	int n=0,prev=0,next=0;
}a[1000005];
int q,cnt=1,m[1000005],t,n,x,y;
int main()
{
	
	cin>>q;
	a[0].n=1;
	m[1]=0;
	for(int i=1;i<=q;i++)
	{
		
		cin>>t;
		if(t==1)
		{
			cin>>x>>y;
			if(a[m[x]].next!=0)
			a[a[m[x]].next].prev=cnt;
			a[m[x]].next=cnt;
			m[y]=cnt;
			a[m[y]].n=y;
			a[m[y]].prev=m[x]; 
			cnt++;
		}
		else if(t==2)
		{
			
			cin>>x;
			if(a[m[x]].next==0)
			{
				cout<<"0"<<endl;
			}
			else
			{
				cout<<a[a[m[x]].next].n<<endl;
			}
		} 
		else
		{
			cin>>x;
			    a[m[x]].next=a[a[m[x]].next].next;	
			if(a[a[m[x]].next].next!=0)							
			    a[a[a[m[x]].next].next].prev=m[x];
		}
	}
	return 0;
}