#include #include #include using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 4000000000000000001 template struct potentialized_dsu { public: potentialized_dsu() : _n(0) {} potentialized_dsu(int n) : _n(n), parent_or_size(n, -1), d(n) {} int merge(int a, int b, S v) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); int x = leader(a), y = leader(b); if (x == y) return x; if (-parent_or_size[x] < -parent_or_size[y]){ std::swap(x, y); std::swap(a, b); S t; v = t - v; } v += diff(x,a); v -= diff(y,b); d[y] += d[x] + v; parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < _n); assert(0 <= b && b < _n); return leader(a) == leader(b); } int leader(int a) { assert(0 <= a && a < _n); if (parent_or_size[a] < 0) return a; int l = leader(parent_or_size[a]); if(parent_or_size[a] != l){ d[a] += d[parent_or_size[a]]; parent_or_size[a] = l; } return parent_or_size[a]; } int size(int a) { assert(0 <= a && a < _n); return -parent_or_size[leader(a)]; } S diff(int a,int b){ assert(0 <= a && a < _n); assert(0 <= b && b < _n); leader(a); leader(b); return d[b] - d[a]; } std::vector> groups() { std::vector leader_buf(_n), group_size(_n); for (int i = 0; i < _n; i++) { leader_buf[i] = leader(i); group_size[leader_buf[i]]++; } std::vector> result(_n); for (int i = 0; i < _n; i++) { result[i].reserve(group_size[i]); } for (int i = 0; i < _n; i++) { result[leader_buf[i]].push_back(i); } result.erase( std::remove_if(result.begin(), result.end(), [&](const std::vector& v) { return v.empty(); }), result.end()); return result; } int _n; // root node: -1 * component size // otherwise: parent std::vector parent_or_size; std::vector d; }; struct xorint{ using mytype = xorint; int v = 0; mytype operator+(mytype another)const{ return (mytype(*this)+=another); } mytype &operator+=(const mytype &another){ (*this).v ^= another.v; return (*this); } mytype operator-(mytype another)const{ return (mytype(*this)-=another); } mytype &operator-=(const mytype &another){ (*this).v ^= another.v; return (*this); } }; int main(){ int n,q; cin>>n>>q; potentialized_dsu D(n); int cn = n; vector is; mint ans = 1; rep(i,q){ //cout<<"A"<>t; if(t<=2){ int u,v; cin>>u>>v; u--,v--; xorint x; x.v = 0; if(t==2)x.v = 1; if(D.same(u,v)){ if(D.diff(u,v).v!=x.v)ans = 0; } else{ cn--; D.merge(u,v,x); is.push_back(u); is.push_back(v); } } else{ ans = 1; rep(j,is.size()){ D.parent_or_size[is[j]] = -1; D.d[is[j]] = xorint(); } cn = n; is.clear(); } if(ans!=0){ cout<