public import std; DList!string scan_buffer; DList!char char_buffer; static this() { scan_buffer = DList!(string)(); char_buffer = DList!(char)(); } void cin()() { } void cin(T, A...)(ref T a, ref A tail) { import std.traits : isArray; static if (typeof(a).stringof == "string") { if (!char_buffer.empty) { a = char_buffer.array.map!(x => x.to!string).join(); char_buffer.clear(); } else { while (scan_buffer.empty) { foreach (t; readln.split) { if (t.length == 0) { continue; } scan_buffer.insert(t); } } auto token = scan_buffer.front; scan_buffer.removeFront(); a = token; } } else static if (typeof(a).stringof == "char") { if (!char_buffer.empty) { a = char_buffer.front(); char_buffer.removeFront(); } else { while (scan_buffer.empty) { foreach (t; readln.split) { if (t.length == 0) { continue; } scan_buffer.insert(t); } } auto token = scan_buffer.front; scan_buffer.removeFront(); a = token[0]; if (token.length > 1) { foreach (c; token[1 .. $]) { char_buffer.insertBack(c); } } } } else static if (typeof(a).stringof == "char[]") { if (a.length == 0) { string token; cin(token); foreach (c; token) { a ~= c; } } else { foreach (ref v; a) { cin(v); } } } else static if (isArray!(typeof(a))) { foreach (ref v; a) { cin(v); } } else static if (isTuple!(typeof(a))) { foreach (i, _; a) { cin(a[i]); } } else { if (!char_buffer.empty) { writeln(char_buffer.array.map!(x => x.to!string)); a = char_buffer.array.map!(x => x.to!string).join().to!T; char_buffer.clear(); } else { while (scan_buffer.empty) { foreach (t; readln.split) { if (t.length == 0) { continue; } scan_buffer.insert(t); } } auto token = scan_buffer.front; scan_buffer.removeFront(); a = token.to!T; } } cin(tail); } bool chmin(T)(ref T a, T b) { if (a > b) { a = b; return true; } return false; } bool chmax(T)(ref T a, T b) { if (a < b) { a = b; return true; } return false; } alias PQueue(T = long, alias less = "a p[y]) swap(x, y); if (p[x] == p[y]) { history.insertBack(P(x, p[x])); p[x]--; } history.insertBack(P(y, p[y])); p[y] = x; } int leader(int x) { if (p[x] < 0) return x; else return leader(p[x]); } void snapshot() { history.clear(); } void rollback() { while (!history.empty()) { auto pa = history.back(); history.removeBack(); p[pa[0]] = pa[1]; } } } import std.typecons : Tuple; ulong safeMod(long x, long m) @safe pure nothrow @nogc { x %= m; if (x < 0) x += m; return x; } ulong[2] umul128(ulong a, ulong b) @safe @nogc pure nothrow { immutable ulong au = a >> 32; immutable ulong bu = b >> 32; immutable ulong al = a & ((1UL << 32) - 1); immutable ulong bl = b & ((1UL << 32) - 1); ulong t = al * bl; immutable ulong w3 = t & ((1UL << 32) - 1); ulong k = t >> 32; t = au * bl + k; k = t & ((1UL << 32) - 1); immutable ulong w1 = t >> 32; t = al * bu + k; k = t >> 32; return [au * bu + w1 + k, t << 32 + w3]; } struct Barrett { uint _m; ulong im; this(uint m) @safe @nogc pure nothrow { _m = m; im = (cast(ulong)(-1)) / m + 1; } uint umod() @safe @nogc pure nothrow { return _m; } uint mul(uint a, uint b) @safe @nogc pure nothrow { ulong z = a; z *= b; immutable ulong x = umul128(z, im)[0]; uint v = cast(uint)(z - x * _m); if (_m <= v) v += _m; return v; } } long ctPowMod(long x, long n, int m) @safe pure nothrow @nogc { if (m == 1) return 0; uint _m = cast(uint) m; ulong r = 1; ulong y = safeMod(x, m); while (n) { if (n & 1) r = (r * y) % _m; y = (y * y) % _m; n >>= 1; } return r; } bool ctIsPrime(int n) @safe pure nothrow @nogc { if (n <= 1) return false; if (n == 2 || n == 7 || n == 61) return true; if (n % 2 == 0) return false; long d = n - 1; while (d % 2 == 0) d /= 2; foreach (a; [2, 7, 61]) { long t = d; long y = ctPowMod(a, t, n); while (t != n - 1 && y != 1 && y != n - 1) { y = y * y % n; t <<= 1; } if (y != n - 1 && t % 2 == 0) { return false; } } return true; } enum bool isPrime(int n) = ctIsPrime(n); Tuple!(long, long) invGcd(long a, long b) @safe pure nothrow @nogc { a = safeMod(a, b); if (a == 0) return Tuple!(long, long)(b, 0); long s = b, t = a, m0 = 0, m1 = 1; while (t) { immutable long u = s / t; s -= t * u; m0 -= m1 * u; long tmp = s; s = t; t = tmp; tmp = m0; m0 = m1; m1 = tmp; } if (m0 < 0) m0 += b / s; return Tuple!(long, long)(s, m0); } int ctPrimitiveRoot(int m) @safe pure nothrow @nogc { if (m == 2) return 1; if (m == 167_772_161) return 3; if (m == 469_762_049) return 3; if (m == 754_974_721) return 11; if (m == 998_244_353) return 3; int[20] divs; divs[0] = 2; int cnt = 1; int x = (m - 1) / 2; while (x % 2 == 0) x /= 2; for (int i = 3; (cast(long) i) * i <= x; i += 2) if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) x /= i; } if (x > 1) divs[cnt++] = x; for (int g = 2;; g++) { bool ok = true; foreach (i; 0 .. cnt) if (ctPowMod(g, (m - 1) / divs[i], m) == 1) { ok = false; break; } if (ok) return g; } } enum primitiveRoot(int m) = ctPrimitiveRoot(m); struct StaticModInt(int m) if (1 <= m) { import std.traits : isSigned, isUnsigned, isSomeChar; alias mint = StaticModInt; public: static int mod() { return m; } static mint raw(int v) { mint x; x._v = v; return x; } this(T)(T v) if (isSigned!T) { long x = cast(long)(v % cast(long)(umod())); if (x < 0) x += umod(); _v = cast(uint)(x); } this(T)(T v) if (isUnsigned!T || isSomeChar!T) { _v = cast(uint)(v % umod()); } this(bool v) { _v = cast(uint)(v) % umod(); } auto opAssign(T)(T v) if (isSigned!T || isUnsigned!T || isSomeChar!T || is(T == bool)) { return this = mint(v); } inout uint val() pure { return _v; } ref mint opUnary(string op)() pure nothrow @safe if (op == "++") { _v++; if (_v == umod()) _v = 0; return this; } ref mint opUnary(string op)() pure nothrow @safe if (op == "--") { if (_v == 0) _v = umod(); _v--; return this; } mint opUnary(string op)() if (op == "+" || op == "-") { mint x; return mixin("x " ~ op ~ " this"); } ref mint opOpAssign(string op, T)(T value) if (!is(T == mint)) { mint y = value; return opOpAssign!(op)(y); } ref mint opOpAssign(string op, T)(T value) if (op == "+" && is(T == mint)) { _v += value._v; if (_v >= umod()) _v -= umod(); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "-" && is(T == mint)) { _v -= value._v; if (_v >= umod()) _v += umod(); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "*" && is(T == mint)) { ulong z = _v; z *= value._v; _v = cast(uint)(z % umod()); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "/" && is(T == mint)) { return this = this * value.inv(); } ref mint opOpAssign(string op, T)(T value) if (op == "^^" && (is(T == int) || is(T == long))) { return this = this.pow(value); } mint pow(long n) const pure { assert(0 <= n); mint x = this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } mint inv() const pure { static if (prime) { assert(_v); return pow(umod() - 2); } else { auto eg = invGcd(_v, mod()); assert(eg[0] == 1); return mint(eg[1]); } } mint opBinary(string op, R)(const R value) const pure if (op == "+" || op == "-" || op == "*" || op == "/") { static if (is(R == mint)) { mint x; x += this; return x.opOpAssign!(op)(value); } else { mint x; x += this; mint y = value; return x.opOpAssign!(op)(y); } } mint opBinary(string op, R)(const R value) const pure if (op == "^^") { return pow(value); } mint opBinaryRight(string op, L)(const L value) const if (!is(L == mint)) { mint y = value; return y.opBinary!(op)(this); } bool opEquals(R)(const R value) const { static if (is(R == mint)) { return _v == value._v; } else { mint y = mint(value); return this == y; } } private: uint _v; uint umod() pure const { return m; } enum bool prime = isPrime!(m); } struct DynamicModInt(int id) { import std.traits : isSigned, isUnsigned, isSomeChar; alias mint = DynamicModInt; public: static int mod() { return bt.umod(); } static void setMod(int m) { assert(1 <= m); bt = Barrett(m); } static mint raw(int v) { mint x; x._v = v; return x; } this(T)(T v) if (isSigned!T) { long x = cast(long)(v % cast(long)(umod())); if (x < 0) x += umod(); _v = cast(uint)(x); } this(T)(T v) if (isUnsigned!T || isSomeChar!T) { _v = cast(uint)(v % umod()); } this(bool v) { _v = cast(uint)(v) % umod(); } auto opAssign(T)(T v) if (isSigned!T || isUnsigned!T || isSomeChar!T || is(T == bool)) { return this = mint(v); } inout uint val() { return _v; } ref mint opUnary(string op)() nothrow @safe if (op == "++") { _v++; if (_v == umod()) _v = 0; return this; } ref mint opUnary(string op)() nothrow @safe if (op == "--") { if (_v == 0) _v = umod(); _v--; return this; } mint opUnary(string op)() if (op == "+" || op == "-") { mint x; return mixin("x " ~ op ~ " this"); } ref mint opOpAssign(string op, T)(T value) if (!is(T == mint)) { mint y = value; return opOpAssign!(op)(y); } ref mint opOpAssign(string op, T)(T value) if (op == "+" && is(T == mint)) { _v += value._v; if (_v >= umod()) _v -= umod(); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "-" && is(T == mint)) { _v -= value._v; if (_v >= umod()) _v += umod(); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "*" && is(T == mint)) { _v = bt.mul(_v, value._v); return this; } ref mint opOpAssign(string op, T)(T value) if (op == "/" && is(T == mint)) { return this = this * value.inv(); } ref mint opOpAssign(string op, T)(T value) if (op == "^^" && (is(T == int) || is(T == long))) { return this = this.pow(value); } mint pow(long n) const { assert(0 <= n); mint x = this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; } mint inv() const { auto eg = invGcd(_v, mod()); assert(eg[0] == 1); return mint(eg[1]); } mint opBinary(string op, R)(const R value) if (op == "+" || op == "-" || op == "*" || op == "/") { static if (is(R == mint)) { mint x; x += this; return x.opOpAssign!(op)(value); } else { mint y = value; return opOpAssign!(op)(y); } } mint opBinary(string op, R)(const R value) const if (op == "^^") { return pow(value); } mint opBinaryRight(string op, L)(const L value) const if (!is(L == mint)) { mint y = value; return y.opBinary!(op)(this); } bool opEquals(R)(const R value) const { static if (is(R == mint)) { return _v == value._v; } else { mint y = mint(value); return this == y; } } private: uint _v; static Barrett bt = Barrett(998_244_353); uint umod() { return bt.umod(); } } alias modint998244353 = StaticModInt!(998244353); alias modint1000000007 = StaticModInt!(1000000007); alias modint = DynamicModInt!(-1); alias mint = modint998244353; void main() { int N, Q; cin(N, Q); auto dsu = new RollbackUnionFind(N * 2); int cnt = N; bool zero = false; foreach (q; 0 .. Q) { int k; cin(k); if (k == 1) { int u, v; cin(u, v); u--; v--; if (!dsu.same(u, v)) { dsu.merge(u, v); dsu.merge(u + N, v + N); cnt--; } if (dsu.same(u, u + N)) { zero = true; } if (zero) { 0.writeln; } else { (mint(2) ^^ cnt).val.writeln; } } else if (k == 2) { int u, v; cin(u, v); u--; v--; if (!dsu.same(u, v + N)) { dsu.merge(u, v + N); dsu.merge(u + N, v); cnt--; } if (dsu.same(u, u + N)) { zero = true; } if (zero) { 0.writeln; } else { (mint(2) ^^ cnt).val.writeln; } } else { zero = false; cnt = N; dsu.rollback(); (mint(2) ^^ cnt).val.writeln; } } }