并查集写法，查不出错/yun

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=998244353;
int n,q,lst=0;
int fa[100010]={0},A,B,C,sz[100010],f[100010];
vector<int> G[100010];
void dfs(int u,int Fa){
	fa[u]=Fa;
	for(int v:G[u]) if(v!=Fa) dfs(v,u);
}
int getfa(int x){
	return (x==f[x]?x:f[x]=getfa(f[x]));
}
void Merge(int u,int v){
	G[u].push_back(v);
	G[v].push_back(u);
	int fau=getfa(u),fav=getfa(v);
	//cout<<"!:"<<u<<","<<v<<","<<fau<<","<<fav<<","<<sz[fau]<<","<<sz[fav]<<endl;
	if(sz[fau]<sz[fav]) sz[fav]+=sz[fau],f[fau]=fav,dfs(u,v);
	else sz[fau]+=sz[fav],f[fav]=fau,dfs(v,u);
}
signed main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++) f[i]=i,sz[i]=1;
	while(q--){
		int a,b,c;
		cin>>a>>b>>c;
		A=1+(a*(1+lst)%mod)%2;
		B=1+(b*(1+lst)%mod)%n;
		C=1+(c*(1+lst)%mod)%n;
		if(A==2){
			lst=0;
			if(fa[B]==fa[C]&&fa[B]!=0) lst=fa[B];
			else if(fa[fa[B]]==C) lst=fa[B];
			else if(fa[fa[C]]==B) lst=fa[C];
			cout<<lst<<endl;
		}else Merge(B,C);
	}
	return 0;
}