Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<stack>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 100010

struct node

{

	int c[2],fa;

	bool rev;

	node(){c[0] = c[1] = fa = 0;rev = false;}

}t[MAXN];

bool isroot(int k){return (t[t[k].fa].c[0] != k && t[t[k].fa].c[1] != k);}

int id(int k){return (t[t[k].fa].c[0] == k ? 0 : 1);}

void pushdown(int rt)

{

	if(t[rt].rev)

	{

		t[t[rt].c[0]].rev ^= 1;t[t[rt].c[1]].rev ^= 1;

		swap(t[rt].c[0],t[rt].c[1]);t[rt].rev = false;

	}

	return;

}

void connect(int k,int f,int p){t[k].fa = f;t[f].c[p] = k;return;}

void rotate(int x)

{

	int y = t[x].fa,z = t[y].fa,fx = id(x),fy = id(y);

	if(!isroot(y))t[z].c[fy] = x;

	t[x].fa = z;

	connect(t[x].c[fx ^ 1],y,fx);

	connect(y,x,fx ^ 1);

	return;

}

stack<int> s;

void splay(int x)

{

	s.push(x);

	for(int i = x;!isroot(i);i = t[i].fa)s.push(t[i].fa);

	while(!s.empty()){pushdown(s.top());s.pop();}

	while(!isroot(x))

	{

		int y = t[x].fa;

		if(isroot(y)){rotate(x);break;}

		if(id(x) == id(y)){rotate(y);rotate(x);}

		else{rotate(x);rotate(x);}

	}

	return;

}

int access(int k){int i;for(i = 0;k;i = k,k = t[k].fa){splay(k);t[k].c[1] = i;}return i;}

void makeroot(int k){access(k);splay(k);t[k].rev ^= 1;return;}

int main()

{

	scanf("%d%d",&n,&m);

	char c[10];

	int a,b;

	for(int i = 1;i <= m;++i)

	{

		scanf("%s",c);

		if(c[1] == 'i')

		{

			scanf("%d%d",&a,&b);

			splay(a);t[a].fa = b;

		}

		if(c[1] == 'u')

		{

			scanf("%d",&a);

			access(a);splay(a);

			t[t[a].c[0]].fa = 0;t[a].c[0] = 0;

		}

		if(c[1] == 'c')

		{

			scanf("%d%d",&a,&b);

			access(a);

			printf("%d\n",access(b));

		}

	}

	return 0;

}