RT，思路和这个题解一样

经过验证，这个代码中，树的高度不太对（非 $O(logn)$ ），但是代码基本和题解一样，不知道哪里错了

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fr(ii,ss,tt) for(int ii=ss;ii<=tt;ii++)
#define rf(ii,ss,tt) for(int ii=ss;ii>=tt;ii--)
#define pii pair<int,int>
#define pt printf
#define fi first
#define eb emplace_back
#define se second
#define all(a) begin(a),end(a)
#define File(f1,f2) freopen(f1,"r",stdin),freopen(f2,"w",stdout)
inline void rd() {} template<typename T, typename... args>inline void rd(T&x, args&...y) {
	char ch;
	bool f = 0;
	for (ch = getchar(); ch < '0' || '9' < ch; ch = getchar())if (ch == '-')f = 1;
	for (x = 0; '0' <= ch && ch <= '9'; ch = getchar())x = (x << 1) + (x << 3) + ch - '0';
	if (f)x = -x;
	rd(y...);
}

using Int = long long;
const int N = 1e6 + 33, mod = 998244353;
const int inf = 2e9;
#define int long long
int n, q, last, fa[N];
int findroot(int x) {
	return fa[x] == 0 ? x : findroot(fa[x]);
}
int sz[N];
int s(int i) {
	assert(fa[i] == 0 && sz[i]);
	return sz[i];
}
void lift(int u) {
	if(!u)return;
	lift(fa[u]);
	fa[fa[u]] = u;
}
signed main() {
	rd(n, q);
	fr(i, 1, n)sz[i] = 1;
	fr(i, 1, q) {
		int a, b, c;
		rd(a, b, c);
		int op = 1 + (a * (last + 1) % mod % 2);
		int u = 1 + (b * (last + 1) % mod % n);
		int v = 1 + (c * (last + 1) % mod % n);
		if(op == 1) {
			if(s(findroot(u)) < s(findroot(v)))swap(u, v);
			lift(v);
			//u big   v small
			fa[v] = u;
			sz[findroot(u)] += sz[v];
		} else {
			int ans = 0;
			if(fa[u] == fa[v]) {
				ans = fa[u];
			}
			if(fa[fa[u]] == v) {
				ans = fa[u];
			}
			if(fa[fa[v]] == u) {
				ans = fa[v];
			}
			pt("%lld\n", last = ans);
		}
	}
	return 0;
}