给你一棵树，有 $n$ 个节点。一开始编号越小的节点优先值越大，每次将优先值最大的叶子节点删掉。有 $3$ 种操作：将一个节点的优先值置为最小、询问一个节点被删除的时间、询问两个节点被删除时间的先后关系。

首先可以发现，优先值最小的节点一定是最后被删除。其次，优先值次小的节点删除之前，优先值次小的节点与优先值最小的节点之间的点一定不能被删除。并且除了优先值最小的节点和优先值次小节点与优先值最小节点之间的点，优先值次小节点一定是最晚被删除的。

以此类推，可以推断出从后到前删除的依次是：优先值最小的节点、优先值最小的节点到优先值次小的点、优先值第三小的点到优先值最小的点与优先值次小的点之间的连通块、优先值第四小的点到优先值最小的点与优先值次小的点与优先值第三小的点之间的连通块 $\cdots \cdots$ 。

这个过程类似于把所有点按照优先值从大到小排序，以优先值最小点作为根，然后依次把这些点到根的路径染色。最后的删除顺序就是按照颜色从早到晚，深度从深到浅的顺序删除。

发现这个染色操作类似于 LCT 中的 access 操作。因此我们构建一颗 LCT，其中的每个 splay 存储着一段颜色相同的路径。每个点的删除顺序，就是 LCT 中所有比它染色早的点的总和加上与他同种颜色的点中深度大于它的。

后者可以直接用 splay 维护，对于前者我们用一个树状数组记录每个颜色有多少个点即可。

只有在虚实边切换时颜色块内的信息才会改变，虚边的数量均摊下来是 $logn$ 的，加上 splay 带个 $log$ 这一部分的复杂度是 $log^2n$ 。

对于修改操作，将一个点的优先值置为最低相当于将这个点置为根。因此加一个换根操作即可。

$Code$

#include<bits/stdc++.h>
#define int long long
#define N 1000010
using namespace std;
int n,m;
int cnt,head[N],to[N<<1],nxt[N<<1];
void insert(int u,int v) {
	cnt++;
	to[cnt]=v;
	nxt[cnt]=head[u];
	head[u]=cnt;
} 

struct TreeAg{
	int c[N];
	int lowbit(int x) {return x-=x&(x-1);}
	void init() {
		for(int i=1; i<=n; i++) c[i]=1;
		for(int i=1; i<=n+m; i++) if(i+lowbit(i)<=n+m) c[i+lowbit(i)]+=c[i];
	}
	void add(int pos,int val) {
		while(pos<=n+m) c[pos]+=val,pos+=lowbit(pos);
	}
	int query(int pos) {
		int res=0;
		while(pos) res+=c[pos],pos-=lowbit(pos);
		return res;
	} 
}tr;

namespace LinkCutTree{
	int val[N],c[N][2],laz[N],f[N],tag[N],siz[N];
	bool ntrt(int x) {return c[f[x]][0]==x||c[f[x]][1]==x;}
	void pushup(int x) {siz[x]=siz[c[x][0]]+siz[c[x][1]]+1;}
	void rev(int x) {
		swap(c[x][0],c[x][1]);
		laz[x]^=1;
	}
	void pushdown(int x) {
		if(laz[x]) {
			if(c[x][0]) rev(c[x][0]);
			if(c[x][1]) rev(c[x][1]);
			laz[x]=0;
		}
		if(tag[x]) {
			if(c[x][0]) val[c[x][0]]=tag[c[x][0]]=tag[x];
			if(c[x][1]) val[c[x][1]]=tag[c[x][1]]=tag[x];
			tag[x]=0;
		}
	}
	void rotate(int x) {
		int y=f[x],z=f[y],k=c[y][1]==x,w=c[x][!k];
		if(ntrt(y)) c[z][c[z][1]==y]=x;
		c[x][!k]=y,c[y][k]=w;
		if(w) f[w]=y;
		f[y]=x,f[x]=z;
		pushup(y);
	}
	int sk[N];
	void splay(int x) {
		int tmp=x,tot=0;
		sk[++tot]=tmp;
		while(ntrt(tmp)) sk[++tot]=tmp=f[tmp];
		while(tot) pushdown(sk[tot--]);
		while(ntrt(x)) {
			int y=f[x],z=f[y];
			if(ntrt(y)) rotate((c[z][0]==y)^(c[y][0]==x)?x:y);
			rotate(x);
		}
		pushup(x);
	}
	void access(int x) {
		int last_siz=0;
		for(int y=0; x; x=f[y=x]) {
			splay(x),c[x][1]=y,pushup(x);
			tr.add(val[x],last_siz-siz[x]);
			last_siz=siz[x];
		}
	}
	void makeroot(int x,int num) {
		access(x),splay(x);
		tr.add(num,siz[x]);
		rev(x);
		val[x]=tag[x]=num;
	}
}
using namespace LinkCutTree;
void dfs(int now) {
//	cout<<now<<endl
	siz[now]=1,val[now]=now;
	for(int i=head[now]; i; i=nxt[i]) if(to[i]!=f[now])
		f[to[i]]=now,dfs(to[i]);
}
char opt[10];
signed main() {
//	freopen("magician.in","r",stdin);
//	freopen("magician.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	tr.init();
	for(int i=1; i<n; i++) {
		int u,v;
		scanf("%lld%lld",&u,&v);
		insert(u,v);
		insert(v,u);
	}
	dfs(1);
	for(int i=2; i<=n; i++) makeroot(i,i-1);
	int tot=n;
	for(int i=1; i<=m; i++) {
		scanf("%s",opt);
		if(opt[0]=='c') {
			int x,y;
			scanf("%lld%lld",&x,&y);
		    splay(x);
			int sx=siz[c[x][1]]+1+tr.query(val[x]-1);
			splay(y);
			int sy=siz[c[y][1]]+1+tr.query(val[y]-1);
			if(sx<sy) printf("%lld\n",x);
			else printf("%lld\n",y);
		} 
		else if(opt[0]=='u'){
			int x;
			scanf("%lld",&x);
			makeroot(x,tot++);
		} else {
			int x;
			scanf("%lld",&x);
			splay(x);
			printf("%lld\n",siz[c[x][1]]+1+tr.query(val[x]-1));
		}
	}
	return 0;
}