#include
    
     #include
     
      using namespace std;int shu[80004][2],n,size,root,kind,zhi[80004],fa[80004],sum=0;int b1,b2;void xuan(int a1){	int a2,a3,l,r;	a2=fa[a1];	a3=fa[a2];	if(shu[a2][0]==a1)	  l=0;	else      l=1;	r=l^1;		if(a2==root)	  root=a1;	else	  if(shu[a3][0]==a2)	    shu[a3][0]=a1;	  else	    shu[a3][1]=a1;	fa[a1]=a3;	fa[a2]=a1;	shu[a2][l]=shu[a1][r];	fa[shu[a1][r]]=a2;	shu[a1][r]=a2;	return;}void zhuan(int a1){	int y,z;	for(;a1!=root;)     {      y=fa[a1];	  z=fa[y];	 	  if(y!=root)	    if((shu[y][0]==a1)^(shu[z][0]==y))	  	  xuan(a1);	    else	      xuan(y);	  xuan(a1);	}}void cha(int &a1,int a2,int a3){	if(a1==0)	  {	  	size++;	  	a1=size;	  	zhi[a1]=a2;	  	fa[a1]=a3;	  	zhuan(a1);	    return;	  }	if(a2
      
       =a2)	  {	  	b2=a1;	  	hou(shu[a1][0],a2);	  }	else	  hou(shu[a1][1],a2);}void del(int a1){	zhuan(a1);	if(shu[a1][0]*shu[a1][1]==0)    	root=shu[a1][0]+shu[a1][1];	else	  {	  	int k=shu[a1][1];	  	while(shu[k][0])		  k=shu[k][0];	  	  shu[k][0]=shu[a1][0];	  	  fa[shu[a1][0]]=k;	  	  root=shu[a1][1];		} 	fa[root]=0;	return; }int main(){	scanf("%d",&n);	for(int i=0;i