我们考虑建出操作树，先进行一次 $\text{dfs}$，将加边操作判断是否合法（是否已连通），处理出操作树上每个加边操作并查集的根，询问操作并查集的根。

将权值离散化，使得每个权值唯一对应一个点，对值域分块。

对于每个值域块进行一次 $\text{dfs}$，得出每个询问的答案在哪一个值域块内。

对操作树分块，这里分块的要求是选出 $O(\frac{m}{B})$ 个点使得树上任意一个点存在一个不超过 $O(B)$ 级祖先为关键点，$B$ 取 $\sqrt{m}$。

我们称一个点所属的块的根为离它最近的为关键点的祖先（包括自己），有同一个所属的块的根的节点属于同一块。

对于每一个块，我们可以 $O(m)$ 处理出操作到这个块根时，每个点所属的并查集的根。块内每个询问的状态是从根处状态合并 $O(B)$ 次连通块形成的，我们把这 $O(B)$ 次合并连通块拿出来，$\text{BFS}$ 一遍就可以知道哪些并查集的根与询问节点属于同一连通块，枚举答案所在值域块内点，得到答案，我们就完成了一个时间 $O(n\sqrt{n})$，空间 $O(n)$ 的算法，$n,m$ 同阶。

ps：我不知道这题啥毛病，我值域分块块长 $3500$ 最快。

#include<cstdio>
#include<utility>
#include<algorithm>
#include<vector>
int const BLK=3500,BKK=400;
int qool[100010],*v[100010],*ql=qool;
int ss[100010];
int n,m,op[100010],A[100010],B[100010],val[100010],f[100010],sz[100010],psz[100010],ans[100010];
int *h[100010];
int pool[600010],*pl;
std::pair<int,int> p[100010];
int find(int x){
	while(x!=f[x])x=f[x];
	return x;
}
bool merge(int &x,int &y){
	x=find(x),y=find(y);
	if(x==y) return false;
	if(sz[x]>sz[y]) std::swap(x,y);
	f[x]=y,sz[y]+=sz[x];
	return true;
}
int d[100010],book[100010],bel[100010],blk,L[100010],R[100010],fa[100010],BEL[100010],bcnt;
void dfs(int x){
	d[x]=1;
	if(op[x]==1) if(!merge(A[x],B[x])) op[x]=0;
	if(op[x]==3){
		A[x]=find(A[x]);
		if(sz[A[x]]<B[x])ans[x]=-1,op[x]=4;
	}
	for(int i=0;i<ss[x];i++)fa[v[x][i]]=x,dfs(v[x][i]),d[x]=std::max(d[v[x][i]]+1,d[x]);
	if(op[x]==1) sz[B[x]]-=sz[A[x]],f[A[x]]=A[x];
	if(d[x]==BKK) d[x]=0,book[x]=1,BEL[x]=++bcnt;
}
int tt;
void dfs1(int x){
	if(op[x]==1) f[A[x]]=B[x],sz[B[x]]+=sz[A[x]];
	if(op[x]==3){
		d[x]+=sz[A[x]];
		if(d[x]>=B[x]) d[x]-=sz[A[x]],ans[x]=tt,op[x]=5;
	}
	for(int i=0;i<ss[x];i++)dfs1(v[x][i]);
	if(op[x]==1) sz[B[x]]-=sz[A[x]],f[A[x]]=A[x];
}
void dfs2(int x){
	for(int i=0;i<ss[x];i++){
		if(!BEL[v[x][i]]) BEL[v[x][i]]=BEL[x];
		dfs2(v[x][i]);
	}
}
int col[100010];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&p[i].first),p[i].second=i;
	std::sort(p+1,p+n+1);
	for(int i=1;i<=n;i++) val[p[i].second]=i;
	for(int i=1;i<=n;i++) f[i]=i,sz[i]=1,bel[i]=(i-1)/BLK+1;
	blk=bel[n];
	for(int i=1;i<=n;i++)R[bel[i]]=i;
	for(int i=n;i;i--)L[bel[i]]=i;
	for(int i=1;i<=m;i++){
		scanf("%d",op+i);
		if(op[i]==1) ++ss[i-1],scanf("%d%d",A+i,B+i);
		else if(op[i]==2) scanf("%d",A+i),++ss[A[i]];
		else ++ss[i-1],scanf("%d%d",A+i,B+i);
	}
	for(int i=0;i<=m;i++)v[i]=ql,ql+=ss[i],ss[i]=0;
	for(int i=1;i<=m;i++)
		if(op[i]==1) v[i-1][ss[i-1]++]=i;
		else if(op[i]==2) v[A[i]][ss[A[i]]++]=i;
		else v[i-1][ss[i-1]++]=i;
	fa[0]=-1;
	dfs(0);
	BEL[0]=++bcnt;
	book[0]=1;
	for(int i=0;i<=m;i++) d[i]=0;
	for(int i=1;i<=blk;i++){
		for(int j=1;j<=n;j++)f[j]=j,sz[j]=val[j]>=L[i]&&val[j]<=R[i];
		tt=i;
		dfs1(0);
	}
	dfs2(0);
	for(int u=0;u<=m;u++)if(book[u]){
		static int st[100010],tp,COL[100010];
		tp=0;
		for(int i=1;i<=n;i++)f[i]=i,COL[i]=0;
		for(int i=u;~i;i=fa[i])if(op[i]==1)st[++tp]=i;
		for(int i=tp;i;i--)f[A[st[i]]]=B[st[i]];
		for(int i=1;i<=n;i++)if(f[i]==i) COL[i]=i;
		for(int i=1;i<=n;i++)if(!COL[i]){
			tp=0;
			int e=i;
			while(!COL[e])st[++tp]=e,e=f[e];
			e=COL[e];
			for(int i=1;i<=tp;i++)COL[st[i]]=e;
		}
		for(int v=1;v<=m;v++)if(op[v]==5&&BEL[v]==BEL[u]){
			static int que[100010],vis[100010],sz[100010],dt[100010];
			tp=0;
			for(int i=v;i!=u;i=fa[i])if(op[i]==1)st[++tp]=i;
			pl=pool;
			for(int i=tp;i;i--){
				if(dt[A[st[i]]]!=v) dt[A[st[i]]]=v,vis[A[st[i]]]=sz[A[st[i]]]=0,h[A[st[i]]]=pl,pl+=401;
				if(dt[B[st[i]]]!=v) dt[A[st[i]]]=v,vis[B[st[i]]]=sz[B[st[i]]]=0,h[B[st[i]]]=pl,pl+=401;
			}
			if(dt[A[v]]!=v)sz[A[v]]=0;
			for(int i=tp;i;i--)h[A[st[i]]][sz[A[st[i]]]++]=B[st[i]],h[B[st[i]]][sz[B[st[i]]]++]=A[st[i]];
			int *hd,*tl;
			hd=tl=que;
			*tl++=A[v];
			vis[A[v]]=1;
			while(hd!=tl){
				int x=*hd++;
				col[x]=v;
				for(int i=0;i<sz[x];i++)if(!vis[h[x][i]])*tl++=h[x][i],vis[h[x][i]]=1;
			}
			for(int i=L[ans[v]];;i++)
				if(col[COL[p[i].second]]==v){
					d[v]++;
					if(d[v]==B[v]){
						ans[v]=p[i].first;
						break;
					}
				}
		}
	}
	for(int i=1;i<=m;i++)if(op[i]>=4)printf("%d\n",ans[i]);
	return 0;
}