結果
問題 | No.2588 Increasing Record |
ユーザー | tonegawa |
提出日時 | 2023-12-16 03:18:08 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 44,937 bytes |
コンパイル時間 | 2,152 ms |
コンパイル使用メモリ | 160,740 KB |
実行使用メモリ | 50,508 KB |
最終ジャッジ日時 | 2024-09-27 07:21:45 |
合計ジャッジ時間 | 16,081 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 WA * 29 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <array>#include <tuple>#include <stack>#include <queue>#include <deque>#include <algorithm>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <bitset>#include <cmath>#include <functional>#include <cassert>#include <climits>#include <iomanip>#include <numeric>#include <memory>#include <random>#include <thread>#include <chrono>#define allof(obj) (obj).begin(), (obj).end()#define range(i, l, r) for(int i=l;i<r;i++)#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))#define bit_kth(i, k) ((i >> k)&1)#define bit_highest(i) (i?63-__builtin_clzll(i):-1)#define bit_lowest(i) (i?__builtin_ctzll(i):-1)#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))using ll = long long;using ld = long double;using ul = uint64_t;using pi = std::pair<int, int>;using pl = std::pair<ll, ll>;using namespace std;template<typename F, typename S>std::ostream &operator<<(std::ostream &dest, const std::pair<F, S> &p){dest << p.first << ' ' << p.second;return dest;}template<typename T>std::ostream &operator<<(std::ostream &dest, const std::vector<std::vector<T>> &v){int sz = v.size();if(sz==0) return dest;for(int i=0;i<sz;i++){int m = v[i].size();for(int j=0;j<m;j++) dest << v[i][j] << (i!=sz-1&&j==m-1?'\n':' ');}return dest;}template<typename T>std::ostream &operator<<(std::ostream &dest, const std::vector<T> &v){int sz = v.size();if(sz==0) return dest;for(int i=0;i<sz-1;i++) dest << v[i] << ' ';dest << v[sz-1];return dest;}template<typename T, size_t sz>std::ostream &operator<<(std::ostream &dest, const std::array<T, sz> &v){if(sz==0) return dest;for(int i=0;i<sz-1;i++) dest << v[i] << ' ';dest << v[sz-1];return dest;}template<typename T>std::ostream &operator<<(std::ostream &dest, const std::set<T> &v){for(auto itr=v.begin();itr!=v.end();){dest << *itr;itr++;if(itr!=v.end()) dest << ' ';}return dest;}template<typename T, typename E>std::ostream &operator<<(std::ostream &dest, const std::map<T, E> &v){for(auto itr=v.begin();itr!=v.end();){dest << '(' << itr->first << ", " << itr->second << ')';itr++;if(itr!=v.end()) dest << '\n';}return dest;}std::ostream &operator<<(std::ostream &dest, __int128_t value) {std::ostream::sentry s(dest);if (s) {__uint128_t tmp = value < 0 ? -value : value;char buffer[128];char *d = std::end(buffer);do {--d;*d = "0123456789"[tmp % 10];tmp /= 10;} while (tmp != 0);if (value < 0) {--d;*d = '-';}int len = std::end(buffer) - d;if (dest.rdbuf()->sputn(d, len) != len) {dest.setstate(std::ios_base::badbit);}}return dest;}template<typename T>vector<T> make_vec(size_t sz, T val){return std::vector<T>(sz, val);}template<typename T, typename... Tail>auto make_vec(size_t sz, Tail ...tail){return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));}template<typename T>vector<T> read_vec(size_t sz){std::vector<T> v(sz);for(int i=0;i<(int)sz;i++) std::cin >> v[i];return v;}template<typename T, typename... Tail>auto read_vec(size_t sz, Tail ...tail){auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);for(int i=0;i<(int)sz;i++) v[i] = read_vec<T>(tail...);return v;}long long max(long long a, int b){return std::max(a, (long long)b);}long long max(int a, long long b){return std::max((long long)a, b);}long long min(long long a, int b){return std::min(a, (long long)b);}long long min(int a, long long b){return std::min((long long)a, b);}long long modulo(long long a, long long m){a %= m; return a < 0 ? a + m : a;}void io_init(){std::cin.tie(nullptr);std::ios::sync_with_stdio(false);}#include <limits>struct point_min_range_min{template<typename T>static T id(){return std::numeric_limits<T>::max();}template<typename T>static T update(T a, T b){return std::min(a, b);}template<typename T>static T merge(T a, T b){return std::min(a, b);}};struct point_min_range_second_min{template<typename T>static T id(){return {std::numeric_limits<long long>::max(), std::numeric_limits<long long>::max()};}template<typename T>static T update(T a, T b){if(a.first <= b.first) return {a.first, std::min(a.second, b.first)};else return {b.first, std::min(a.first, b.second)};}template<typename T>static T merge(T a, T b){if(a.first <= b.first) return {a.first, std::min(a.second, b.first)};else return {b.first, std::min(a.first, b.second)};}};struct point_max_range_max{template<typename T>static T id(){return std::numeric_limits<T>::min();}template<typename T>static T update(T a, T b){return std::max(a, b);}template<typename T>static T merge(T a, T b){return std::max(a, b);}template<typename T>static T flip(T a){return a;}};struct point_max_range_second_max{template<typename T>static T id(){return {std::numeric_limits<long long>::min(), std::numeric_limits<long long>::min()};}template<typename T>static T update(T a, T b){if(a.first >= b.first) return {a.first, std::min(a.second, b.first)};else return {b.first, std::min(a.first, b.second)};}template<typename T>static T merge(T a, T b){if(a.first >= b.first) return {a.first, std::min(a.second, b.first)};else return {b.first, std::min(a.first, b.second)};}};struct point_mul_range_mul{template<typename T>static T id(){return 1;}template<typename T>static T update(T a, T b){return a * b;}template<typename T>static T merge(T a, T b){return a * b;}};struct point_add_range_min{template<typename T>static T id(){return std::numeric_limits<T>::max();}template<typename T>static T update(T a, T b){if(a == id<T>()) return b;else if(b == id<T>()) return a;return a + b;}template<typename T>static T merge(T a, T b){return std::min(a, b);}};struct point_add_range_max{template<typename T>static T id(){return std::numeric_limits<T>::min();}template<typename T>static T update(T a, T b){if(a == id<T>()) return b;else if(b == id<T>()) return a;return a + b;}template<typename T>static T merge(T a, T b){return std::max(a, b);}};struct point_add_range_sum{template<typename T>static T id(){return 0;}template<typename T>static T update(T a, T b){return a + b;}template<typename T>static T merge(T a, T b){return a + b;}template<typename T>static T flip(T a){return a;}};struct point_set_range_composite{static constexpr int mod = 998244353;template<typename T>static T id(){return {1, 0};}template<typename T>static T update(T a, T b){return b;}template<typename T>static T merge(T a, T b){int xy = ((long long)a.first * b.first) % mod;int ab = ((long long)a.second * b.first + b.second) % mod;return {xy, ab};}};struct excess_value{int rank, sum, minl, maxr;excess_value(){}excess_value(bool f): rank(f), sum(f ? 1 : -1), minl(sum), maxr(sum){}excess_value(int a, int b, int c, int d): rank(a), sum(b), minl(c), maxr(d){}};struct point_set_range_excess_value{const static int inf = std::numeric_limits<int>::max() / 2;template<typename T>static T id(){// '('を1, ')'を -1としたときの{1の数, 和, 左を固定したsumのmin, 右を固定したsumのmin}return {inf, 0, 0, 0};}template<typename T>static T update(T a, T b){if(a.rank == inf) return b;if(b.rank == inf) return a;return {a.rank + b.rank, a.sum + b.sum, std::min(a.minl, a.sum + b.minl), std::max(b.maxr, a.maxr + b.sum)};}template<typename T>static T merge(T a, T b){if(a.rank == inf) return b;if(b.rank == inf) return a;return {a.rank + b.rank, a.sum + b.sum, std::min(a.minl, a.sum + b.minl), std::max(b.maxr, a.maxr + b.sum)};}};struct point_set_range_composite_flip{static constexpr int mod = 998244353;template<typename T>static T id(){return {1, 0, 0};}template<typename T>static T update(T a, T b){return b;}template<typename T>static T flip(T a){return {a[0], a[2], a[1]};}template<typename T>static T merge(T a, T b){int xy = ((long long)a[0] * b[0]) % mod;int ab = ((long long)a[1] * b[0] + b[1]) % mod;int ba = ((long long)b[2] * a[0] + a[2]) % mod;return {xy, ab, ba};}};// merge(a, b) = max(0, a + b)の場合, {x, 0}で初期化struct hawker{static constexpr long long minf = std::numeric_limits<long long>::min() / 2;template<typename T>static T id(){return {0, minf};}template<typename T>static T update(T a, T b){return {a.first + b.first, std::max(a.second + b.first, b.second)};}template<typename T>static T merge(T a, T b){return {a.first + b.first, std::max(a.second + b.first, b.second)};}};struct point_add_range_gcd{template<typename Val>static Val __binary_gcd(Val a, Val b){if(!a || !b) return !a ? b : a;if(a < 0) a *= -1;if(b < 0) b *= -1;int shift = __builtin_ctzll(a | b); // [1] gcd(2a', 2b') = 2 * gcd(a', b')a >>= __builtin_ctzll(a);do{// if b is odd// gcd(2a', b) = gcd(a', b), if a = 2a'(a is even)// gcd(a, b) = gcd(|a - b|, min(a, b)), if a is oddb >>= __builtin_ctzll(b); // make b oddif(a > b) std::swap(a, b);b -= a;}while(b); // gcd(a, 0) = areturn a << shift; // [1]}template<typename Val>static Val id(){return 0;}template<typename Val>static Val update(Val a, Val b){return a + b;}template<typename Val>static Val merge(Val a, Val b){return __binary_gcd(a, b);}};// 区間set, これまでにsetした物の中ならどれかを取得struct range_set_get_any{template<typename Val>static Val id1(){return nullptr;}template<typename Lazy>static Lazy id2(){return nullptr;}template<typename Lazy>static Lazy propagate(Lazy l, Lazy x){return (x == nullptr ? l : x);}template<typename Val, typename Lazy>static Val apply(Val v, Lazy x, int l, int r){return (x == nullptr ? v : x);}};struct range_add_range_sum{template<typename T>static T id1(){return T(0);}template<typename E>static E id2(){return E(0);}template<typename T>static T merge(T a, T b){return a + b;}template<typename T, typename E>static T apply(T a, E b, int l, int r){return a + b * (r - l);}template<typename E>static E propagate(E a, E b){return a + b;}template<typename T>static T flip(T a){return a;}};struct range_min_range_min{template<typename T>static T id1(){return std::numeric_limits<T>::max();}template<typename E>static E id2(){return std::numeric_limits<E>::max();}template<typename T>static T merge(T a, T b){return std::min(a, b);}template<typename T, typename E>static T apply(T a, E b, int l, int r){return std::min(a, b);}template<typename E>static E propagate(E a, E b){return std::min(a, b);}};struct range_max_range_max{template<typename T>static T id1(){return std::numeric_limits<T>::min();}template<typename E>static E id2(){return std::numeric_limits<E>::min();}template<typename T>static T merge(T a, T b){return std::max(a, b);}template<typename T, typename E>static T apply(T a, E b, int l, int r){return std::max(a, b);}template<typename E>static E propagate(E a, E b){return std::max(a, b);}};struct range_set_range_min{template<typename T>static T id1(){return std::numeric_limits<T>::max();}template<typename E>static E id2(){return std::numeric_limits<E>::max();}template<typename T>static T merge(T a, T b){return std::min(a, b);}template<typename T, typename E>static T apply(T a, E b, int l, int r){return b;}template<typename E>static E propagate(E a, E b){return b;}};struct range_set_range_sum{template<typename T>static T id1(){return 0;}template<typename E>static E id2(){return std::numeric_limits<E>::max();}template<typename T>static T merge(T a, T b){return a + b;}template<typename T, typename E>static T apply(T a, E b, int l, int r){return b * (r - l);}template<typename E>static E propagate(E a, E b){return b;}};struct range_add_range_max{template<typename T>static T id1(){return std::numeric_limits<T>::min();}template<typename E>static E id2(){return 0;}template<typename T>static T merge(T a, T b){return std::max(a, b);}template<typename T, typename E>static T apply(T a, E b, int l, int r){if(a == id1<T>()) return b;return a + b;}template<typename E>static E propagate(E a, E b){return a + b;}};struct range_add_range_min{template<typename T>static T id1(){return std::numeric_limits<T>::max() / 2;}template<typename E>static E id2(){return 0;}template<typename T>static T merge(T a, T b){return std::min(a, b);}template<typename T, typename E>static T apply(T a, E b, int l, int r){if(a == id1<T>()) return b;return a + b;}template<typename E>static E propagate(E a, E b){return a + b;}};struct range_add_range_argmin{template<typename T>static T id1(){return {std::numeric_limits<long long>::max(), -1} ;}template<typename E>static E id2(){return 0;}template<typename T>static T merge(T a, T b){return std::min(a, b);}template<typename T, typename E>static T apply(T a, E b, int l, int r){if(a == id1<T>()) return a;return {a.first + b, a.second};}template<typename E>static E propagate(E a, E b){return a + b;}};/*#include <array>struct range_affine_range_sum{const static long long MOD = 998244353;template<typename T>static T id1(){return 0;}template<typename E>static E id2(){return E{1, 0};}template<typename T>static T merge(T a, T b){return (a + b) % MOD;}template<typename T, typename E>static T apply(T a, E b, int l, int r){return (a * b[0] + b[1] * (r - l)) % MOD;}template<typename E>static E propagate(E a, E b){return E{(a[0] * b[0]) % MOD, (a[1] * b[0] + b[1]) % MOD};}};*/struct range_affine_range_sum{const static int MOD = 998244353;template<typename T>static T id1(){return 0;}template<typename E>static E id2(){return E{1, 0};}template<typename T>static T merge(T a, T b){return (a + b) % MOD;}template<typename T, typename E>static T apply(T a, E b, int l, int r){return ((long long)a * b.first + (long long)b.second * (r - l)) % MOD;}template<typename E>static E propagate(E a, E b){return E{((long long)a.first * b.first) % MOD, ((long long)a.second * b.first + b.second) % MOD};}};struct range_add_range_min_count{static constexpr int INF = std::numeric_limits<int>::max();template<typename T>static T id1(){return {INF, 0};}template<typename E>static E id2(){return 0;}template<typename T>static T merge(T a, T b){if(a.first != b.first) return a.first < b.first ? a : b;return {a.first, a.second + b.second};}template<typename T, typename E>static T apply(T a, E b, int l, int r){if(a.first == INF) return {b, r - l};return {a.first + b, a.second};}template<typename E>static E propagate(E a, E b){return a + b;}};struct range_composite_lct{static constexpr int MOD = 998244353;template<typename T>// 1x + 0, 1x + 0static T id1(){return std::array<int, 3>{1, 0, 0};}// no usetemplate<typename E>static E id2(){return false;}// b(a(x)), a(b(x))template<typename T>static T merge(T a, T b){int ba1 = ((long long)b[0] * a[0]) % MOD;int ba2 = ((long long)b[0] * a[1] + b[1]) % MOD;int ab2 = ((long long)a[0] * b[2] + a[2]) % MOD;return std::array<int, 3>{ba1, ba2, ab2};}// no usetemplate<typename T, typename E>static T apply(T a, E b, int l, int r){return a;}// no usetemplate<typename E>static E propagate(E a, E b){return false;}//template<typename T>static T flip(T a){return std::array<int, 3>{a[0], a[2], a[1]};}};template<typename monoid, typename Val>struct red_black_tree_monoid{struct node{node *l, *r, *p;bool red;int ra, sz;Val val;// 葉node(Val val): l(nullptr), r(nullptr), p(nullptr), red(false), ra(0), sz(1), val(val){}// 中間ノードnode(node *l, node *r, bool red): l(l), r(r), p(nullptr), red(red), ra(l->ra + !(l->red)), sz(l->sz + r->sz){l->p = r->p = this;val = monoid::template merge<Val>(l->val, r->val);}};static std::vector<node*> stock;static node *reuse(node *a, node *l, node *r, bool red){a->l = l, a->r = r, a->p = nullptr, a->red = red;l->p = r->p = a;a->ra = l->ra + !(l->red);a->sz = l->sz + r->sz;a->val = monoid::template merge<Val>(a->l->val, a->r->val);return a;}node *root;using pn = std::pair<node*, node*>;static node *merge_sub(node *a, node *b){if(a->ra < b->ra){node *c = merge_sub(a, b->l);if(!b->red && c->red && c->l->red){if(!b->r->red){return reuse(c, c->l, reuse(b, c->r, b->r, 1), 0);}else{b->r->red = 0;c->red = 0;return reuse(b, c, b->r, 1);}}else{return reuse(b, c, b->r, b->red);}}else if(a->ra > b->ra){node *c = merge_sub(a->r, b);if(!a->red && c->red && c->r->red){if(!a->l->red){return reuse(c, reuse(a, a->l, c->l, 1), c->r, 0);}else{a->l->red = 0;c->red = 0;return reuse(a, a->l, c, 1);}}else{return reuse(a, a->l, c, a->red);}}else{if(stock.empty()) return new node(a, b, 1);node *u = stock.back();stock.pop_back();return reuse(u, a, b, 1);}}static node *merge(node *a, node *b){if(!a || !b) return !a ? b : a;node *c = merge_sub(a, b);c->red = 0;return c;}static node *as_root(node *a){if(!a) return nullptr;a->red = 0;return a;}static pn split(node *a, int k){int sz = a->sz, szl = (a->l ? a->l->sz : 0);if(k == 0 || k == sz) return (!k ? pn{nullptr, a} : pn{a, nullptr});pn res;if(k < szl){auto [l, r] = split(a->l, k);res = pn{l, merge(r, as_root(a->r))};}else if(k > szl){auto [l, r] = split(a->r, k - szl);res = pn{merge(as_root(a->l), l), r};}else{res = pn{as_root(a->l), as_root(a->r)};}if(a) stock.push_back(a);return res;}void set(node *a, int k, Val x){if(!a->l && !a->r){assert(k == 0);a->val = x;return;}int szl = a->l ? a->l->sz : 0;if(k < szl) set(a->l, k, x);else set(a->r, k - szl, x);a->val = monoid::template merge<Val>(a->l->val, a->r->val);}Val get(node *a, int k){if(!a->l && !a->r){assert(k == 0);return a->val;}int szl = a->l ? a->l->sz : 0;if(k < szl) return get(a->l, k);else return get(a->r, k - szl);}static Val query(node *a, int l, int r){if(!a || l >= r || a->sz <= l || r <= 0) return monoid::template id<Val>();if(l <= 0 && a->sz <= r) return a->val;if(!a->l && !a->r) return a->val;int szl = a->l->sz;if(r <= szl) return query(a->l, l, r);if(szl <= l) return query(a->r, l - szl, r - szl);return monoid::template merge<Val>(query(a->l, l, szl), query(a->r, 0, r - szl));}node *build(const std::vector<Val> &v, int l, int r){if(l == r) return nullptr;if(r - l == 1) return new node(v[l]);int mid = (l + r) / 2;node *L = build(v, l, mid);node *R = build(v, mid, r);return merge(L, R);}red_black_tree_monoid(node *a): root(a){}red_black_tree_monoid(): root(nullptr){}red_black_tree_monoid(const std::vector<Val> &v): root(build(v, 0, v.size())){}int size()const{return root ? root->sz : 0;}void set(int k, Val x){assert(k < size());set(root, k, x);}Val get(int k){assert(k < size());return get(root, k);}// k番目にxを挿入void insert(int k, Val x){auto [a, b] = split(root, k);root = merge(a, merge(new node(x), b));}void erase(int k){assert(root->sz > k);auto [a, b] = split(root, k);assert(b);auto [b2, c] = split(b, 1);root = merge(a, c);if(b2) stock.push_back(b2);}Val query(int l, int r)const{assert(0 <= l && r <= size());return query(root, l, r);}Val query_all(){return !root ? monoid::template id1<Val>() : root->val;}using rbtm = red_black_tree_monoid<monoid, Val>;std::pair<rbtm, rbtm> split(int k){return split(*this, k);}// 2つに分割. 永続でないためこれ自身のaのrootはnullptrになるstatic std::pair<rbtm, rbtm> split(rbtm &a, int k){assert(k <= a.size());auto [l, r] = split(a.root, k);a.root = nullptr;return {rbtm(l), rbtm(r)};}// a, bをマージ. 永続でないためa, bのrootはnullptrになるstatic rbtm merge(rbtm &a, rbtm &b){rbtm res(merge(a.root, b.root));a.root = b.root = nullptr;return res;}};template<typename monoid, typename Val>std::vector<typename red_black_tree_monoid<monoid, Val>::node*> red_black_tree_monoid<monoid, Val>::stock;template<typename monoid, typename Val, typename Lazy>struct lazy_red_black_tree_monoid{struct node{node *l, *r, *p;bool red;int ra, sz;Val val;Lazy lazy;// 葉node(Val val): l(nullptr), r(nullptr), p(nullptr), red(false), ra(0), sz(1), val(val), lazy(monoid::template id2<Lazy>()){}// 中間ノードnode(node *l, node *r, bool red): l(l), r(r), p(nullptr), red(red), ra(l->ra + !(l->red)), sz(l->sz + r->sz), lazy(monoid::template id2<Lazy>()){l->p = r->p = this;val = monoid::template merge<Val>(l->val, r->val);}};static std::vector<node*> stock;static node *reuse(node *a, node *l, node *r, bool red){a->l = l, a->r = r, a->p = nullptr, a->red = red;l->p = r->p = a;a->ra = l->ra + !(l->red);a->sz = l->sz + r->sz;a->val = monoid::template merge<Val>(a->l->val, a->r->val);a->lazy = monoid::template id2<Lazy>();return a;}static void propagate(node *a, Lazy x){a->val = monoid::template apply<Val, Lazy>(a->val, x, 0, a->sz);a->lazy = monoid::template propagate<Lazy>(a->lazy, x);}static void push_down(node *a){if(a->lazy == monoid::template id2<Lazy>()) return;if(a->l) propagate(a->l, a->lazy);if(a->r) propagate(a->r, a->lazy);a->lazy = monoid::template id2<Lazy>();}node *root;using pn = std::pair<node*, node*>;static node *merge_sub(node *a, node *b){if(a->ra < b->ra){push_down(b);node *c = merge_sub(a, b->l);if(!b->red && c->red && c->l->red){if(!b->r->red){return reuse(c, c->l, reuse(b, c->r, b->r, 1), 0);}else{b->r->red = 0;c->red = 0;return reuse(b, c, b->r, 1);}}else{return reuse(b, c, b->r, b->red);}}else if(a->ra > b->ra){push_down(a);node *c = merge_sub(a->r, b);if(!a->red && c->red && c->r->red){if(!a->l->red){return reuse(c, reuse(a, a->l, c->l, 1), c->r, 0);}else{a->l->red = 0;c->red = 0;return reuse(a, a->l, c, 1);}}else{return reuse(a, a->l, c, a->red);}}else{if(stock.empty()) return new node(a, b, 1);node *u = stock.back();stock.pop_back();return reuse(u, a, b, 1);}}static node *merge(node *a, node *b){if(!a || !b) return !a ? b : a;node *c = merge_sub(a, b);c->red = 0;return c;}static node *as_root(node *a){if(!a) return nullptr;a->red = 0;return a;}static pn split(node *a, int k){int sz = a->sz, szl = (a->l ? a->l->sz : 0);if(k == 0 || k == sz) return (!k ? pn{nullptr, a} : pn{a, nullptr});pn res;push_down(a);if(k < szl){auto [l, r] = split(a->l, k);res = pn{l, merge(r, as_root(a->r))};}else if(k > szl){auto [l, r] = split(a->r, k - szl);res = pn{merge(as_root(a->l), l), r};}else{res = pn{as_root(a->l), as_root(a->r)};}if(a) stock.push_back(a);return res;}void set(node *a, int k, Val x){if(!a->l && !a->r){assert(k == 0);a->val = x;return;}push_down(a);int szl = a->l ? a->l->sz : 0;if(k < szl) set(a->l, k, x);else set(a->r, k - szl, x);a->val = monoid::template merge<Val>(a->l->val, a->r->val);}Val get(node *a, int k){if(!a->l && !a->r){assert(k == 0);return a->val;}push_down(a);int szl = a->l ? a->l->sz : 0;if(k < szl) return get(a->l, k);else return get(a->r, k - szl);}static void update(node *a, int l, int r, Lazy x){if(!a || l >= r || a->sz <= l || r <= 0) return;if(l <= 0 && a->sz <= r){propagate(a, x);return;}if(!a->l && !a->r){a->val = monoid::template apply<Val, Lazy>(a->val, x, 0, 1);return;}push_down(a);int szl = a->l->sz;update(a->l, l, r, x);update(a->r, l - szl, r - szl, x);a->val = monoid::template merge<Val>(a->l->val, a->r->val);}static Val query(node *a, int l, int r){if(!a || l >= r || a->sz <= l || r <= 0) return monoid::template id1<Val>();if(l <= 0 && a->sz <= r) return a->val;if(!a->l && !a->r) return a->val;push_down(a);int szl = a->l->sz;if(r <= szl) return query(a->l, l, r);if(szl <= l) return query(a->r, l - szl, r - szl);return monoid::template merge<Val>(query(a->l, l, szl), query(a->r, 0, r - szl));}node *build(const std::vector<Val> &v, int l, int r){if(l == r) return nullptr;if(r - l == 1) return new node(v[l]);int mid = (l + r) / 2;node *L = build(v, l, mid);node *R = build(v, mid, r);return merge(L, R);}lazy_red_black_tree_monoid(node *a): root(a){}lazy_red_black_tree_monoid(): root(nullptr){}lazy_red_black_tree_monoid(const std::vector<Val> &v): root(build(v, 0, v.size())){}int size()const{return root ? root->sz : 0;}void set(int k, Val x){assert(k < size());set(root, k, x);}Val get(int k){assert(k < size());return get(root, k);}// k番目にxを挿入void insert(int k, Val x){auto [a, b] = split(root, k);root = merge(a, merge(new node(x), b));}void erase(int k){assert(root->sz > k);auto [a, b] = split(root, k);assert(b);auto [b2, c] = split(b, 1);root = merge(a, c);if(b2) stock.push_back(b2);}void update(int l, int r, Lazy x){assert(0 <= l && r <= size());return update(root, l, r, x);}Val query(int l, int r)const{assert(0 <= l && r <= size());return query(root, l, r);}void update_all(Lazy x){if(root) propagate(root, x);}Val query_all(){return !root ? monoid::template id1<Val>() : root->val;}using rbtm = lazy_red_black_tree_monoid<monoid, Val, Lazy>;std::pair<rbtm, rbtm> split(int k){return split(*this, k);}// 2つに分割. 永続でないためこれ自身のaのrootはnullptrになるstatic std::pair<rbtm, rbtm> split(rbtm &a, int k){assert(k <= a.size());auto [l, r] = split(a.root, k);a.root = nullptr;return {rbtm(l), rbtm(r)};}rbtm merge(rbtm &b){rbtm res = merge(*this, b);root = b.root = nullptr;return res;}// a, bをマージ. 永続でないためa, bのrootはnullptrになるstatic rbtm merge(rbtm &a, rbtm &b){rbtm res(merge(a.root, b.root));a.root = b.root = nullptr;return res;}};template<typename monoid, typename Val, typename Lazy>std::vector<typename lazy_red_black_tree_monoid<monoid, Val, Lazy>::node*> lazy_red_black_tree_monoid<monoid, Val, Lazy>::stock;template<typename monoid, typename Val>struct union_find_monoid{private:using rbt = red_black_tree_monoid<monoid, Val>;using node = typename rbt::node;std::vector<node*> V;std::unordered_map<node*, int> rev;node *__find(int a){node *v = V[a];while(v->p) v = v->p;return v;}public:union_find_monoid(int n): V(n){for(int i = 0; i < n; i++){V[i] = new node(monoid::template id<Val>());rev.emplace(V[i], i);}}union_find_monoid(const std::vector<Val> &val): V(val.size()){for(int i = 0; i < val.size(); i++){V[i] = new node(val[i]);rev.emplace(V[i], i);}}void unite(int a, int b){node *u = __find(a);node *v = __find(b);if(u == v) return;rbt::merge(u, v);}// 通常のunion-find木ではunite(a, b)後の根はaの根, bの根のうちサイズがあ大きい方であるが, このfindはそのルールを守らない// 同じ木の状態で同じ連結成分の要素から呼ばれると同じ値[0, n)を返すことのみ保証されるint find(int a){node *v = V[a];while(v->p) v = v->p;while(v->l) v = v->l;return rev[v];}bool same(int a, int b){return __find(a) == __find(b);}int size(int a){return __find(a)->sz;}Val query(int a){return __find(a)->val;}Val get(int a){return V[a]->val;}void set(int a, Val x){node *v = V[a];v->val = x;while(v->p){v = v->p;v->val = monoid::template merge<Val>(v->l->val, v->r->val);}}std::vector<int> enumerate(int a){std::vector<int> res;node *v = V[a];while(v->p) v = v->p;std::queue<node*> q;q.push(v);while(!q.empty()){v = q.front();q.pop();if(v->l){q.push(v->l);q.push(v->r);}else{res.push_back(rev[v]);}}return res;}};template<typename monoid, typename Val, typename Lazy>struct lazy_union_find_monoid{private:using rbt = lazy_red_black_tree_monoid<monoid, Val, Lazy>;using node = typename rbt::node;std::vector<node*> V;std::unordered_map<node*, int> rev;node *__find(int a){node *v = V[a];while(v->p) v = v->p;return v;}public:lazy_union_find_monoid(int n): V(n){for(int i = 0; i < n; i++){V[i] = new node(monoid::template id1<Val>());rev.emplace(V[i], i);}}lazy_union_find_monoid(const std::vector<Val> &val): V(val.size()){for(int i = 0; i < val.size(); i++){V[i] = new node(val[i]);rev.emplace(V[i], i);}}void unite(int a, int b){node *u = __find(a);node *v = __find(b);if(u == v) return;rbt::merge(u, v);}// 通常のunion-find木ではunite(a, b)後の根はaの根, bの根のうちサイズがあ大きい方であるが, このfindはそのルールを守らない// 同じ木の状態で同じ連結成分の要素から呼ばれると同じ値[0, n)を返すことのみ保証されるint find(int a){node *v = V[a];while(v->p) v = v->p;while(v->l) v = v->l;return rev[v];}bool same(int a, int b){return __find(a) == __find(b);}int size(int a){return __find(a)->sz;}void update(int a, Lazy x){node *v = __find(a);rbt::propagate(v, x);}Val query(int a){return __find(a)->val;}Val get(int a){std::vector<node*> path;node *v = V[a];while(v->p){v = v->p;path.push_back(v);}int m = path.size();for(int i = m - 1; i >= 0; i--) rbt::push_down(path[i]);return V[a]->val;}void set(int a, Val x){std::vector<node*> path;node *v = V[a];while(v->p){v = v->p;path.push_back(v);}int m = path.size();for(int i = m - 1; i >= 0; i--) rbt::push_down(path[i]);V[a]->val = x;for(int i = 0; i < m; i++) path[i]->val = monoid::template merge<Val>(path[i]->l->val, path[i]->r->val);}std::vector<int> enumerate(int a){std::vector<int> res;node *v = V[a];while(v->p) v = v->p;std::queue<node*> q;q.push(v);while(!q.empty()){v = q.front();q.pop();if(v->l){q.push(v->l);q.push(v->r);}else{res.push_back(rev[v]);}}return res;}};#include <type_traits>#include <ostream>// @param m `1 <= m`constexpr long long safe_mod(long long x, long long m){x %= m;if (x < 0) x += m;return x;}struct barrett{unsigned int _m;unsigned long long im;explicit barrett(unsigned int m) : _m(m), im((unsigned long long)(-1) / m + 1){}unsigned int umod()const{return _m;}unsigned int mul(unsigned int a, unsigned int b)const{unsigned long long z = a;z *= b;#ifdef _MSC_VERunsigned long long x;_umul128(z, im, &x);#elseunsigned long long x = (unsigned long long)(((unsigned __int128)(z) * im) >> 64);#endifunsigned long long y = x * _m;return (unsigned int)(z - y + (z < y ? _m : 0));}};// @param n `0 <= n`// @param m `1 <= m`constexpr long long pow_mod_constexpr(long long x, long long n, int m){if(m == 1) return 0;unsigned int _m = (unsigned int)(m);unsigned long long r = 1;unsigned long long y = safe_mod(x, m);while(n){if (n & 1) r = (r * y) % _m;y = (y * y) % _m;n >>= 1;}return r;}constexpr bool is_prime_constexpr(int n) {if (n <= 1) return false;if (n == 2 || n == 7 || n == 61) return true;if (n % 2 == 0) return false;long long d = n - 1;while (d % 2 == 0) d /= 2;constexpr long long bases[3] = {2, 7, 61};for(long long a : bases){long long t = d;long long y = pow_mod_constexpr(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;}template<int n>constexpr bool is_prime = is_prime_constexpr(n);constexpr int primitive_root_constexpr(int m){if(m == 2) return 1;if(m == 167772161) return 3;if(m == 469762049) return 3;if(m == 754974721) return 11;if(m == 998244353) return 3;int divs[20] = {};divs[0] = 2;int cnt = 1;int x = (m - 1) / 2;while (x % 2 == 0) x /= 2;for(int i = 3; (long 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;for(int i = 0; i < cnt; i++){if(pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1){ok = false;break;}}if(ok)return g;}}template <int m>constexpr int primitive_root = primitive_root_constexpr(m);int ceil_pow2(int n){int x = 0;while ((1U << x) < (unsigned int)(n)) x++;return x;}int bsf(unsigned int n){return __builtin_ctz(n);}// @param b `1 <= b`// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/gconstexpr std::pair<long long, long long> inv_gcd(long long a, long long b){a = safe_mod(a, b);if(a == 0) return {b, 0};long long s = b, t = a;long long m0 = 0, m1 = 1;while (t){long long u = s / t;s -= t * u;m0 -= m1 * u;auto tmp = s;s = t;t = tmp;tmp = m0;m0 = m1;m1 = tmp;}if(m0 < 0) m0 += b / s;return {s, m0};}template<int m>long long modpow(long long a, long long b){assert(0 <= b);assert(0 < m);a = safe_mod(a, m);long long ret = 1;while(b){if(b & 1) ret = (ret * a) % m;a = (a * a) % m;b >>= 1;}return ret;}// @param 0 <= b, 0 < mlong long modpow(long long a, long long b, int m){assert(0 <= b);assert(0 < m);a = safe_mod(a, m);long long ret = 1;while(b){if(b & 1) ret = (ret * a) % m;a = (a * a) % m;b >>= 1;}return ret;}struct modint_base {};struct static_modint_base : modint_base {};template <int m, std::enable_if_t<(1 <= m)>* = nullptr>struct static_modint : static_modint_base{using mint = static_modint;public:static constexpr int mod(){return m;}static mint raw(int v) {mint x;x._v = v;return x;}static_modint(): _v(0){}template <class T>static_modint(T v){long long x = v % (long long)umod();if (x < 0) x += umod();_v = x;}unsigned int val()const{return _v;}mint& operator++(){_v++;if (_v == umod()) _v = 0;return *this;}mint& operator--(){if (_v == 0) _v = umod();_v--;return *this;}mint operator++(int){mint result = *this;++*this;return result;}mint operator--(int){mint result = *this;--*this;return result;}mint& operator+=(const mint& rhs){_v += rhs._v;if (_v >= umod()) _v -= umod();return *this;}mint& operator-=(const mint& rhs){_v -= rhs._v;if (_v >= umod()) _v += umod();return *this;}mint& operator*=(const mint& rhs){unsigned long long z = _v;z *= rhs._v;_v = (unsigned int)(z % umod());return *this;}mint& operator/=(const mint& rhs){return *this = *this * rhs.inv();}mint operator+()const{return *this;}mint operator-()const{return mint() - *this;}mint pow(long 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{if(prime){assert(_v);return pow(umod() - 2);}else{auto eg = inv_gcd(_v, m);assert(eg.first == 1);return eg.second;}}friend mint operator+(const mint& lhs, const mint& rhs){return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs){return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs){return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs){return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs){return lhs._v == rhs._v;}friend bool operator!=(const mint& lhs, const mint& rhs){return lhs._v != rhs._v;}private:unsigned int _v;static constexpr unsigned int umod(){return m;}static constexpr bool prime = is_prime<m>;};template<int id>struct dynamic_modint : modint_base{using mint = dynamic_modint;public:static int mod(){return (int)(bt.umod());}static void set_mod(int m){assert(1 <= m);bt = barrett(m);}static mint raw(int v){mint x;x._v = v;return x;}dynamic_modint(): _v(0){}template <class T>dynamic_modint(T v){long long x = v % (long long)(mod());if (x < 0) x += mod();_v = x;}unsigned int val()const{return _v;}mint& operator++(){_v++;if(_v == umod()) _v = 0;return *this;}mint& operator--(){if (_v == 0) _v = umod();_v--;return *this;}mint operator++(int){mint result = *this;++*this;return result;}mint operator--(int){mint result = *this;--*this;return result;}mint& operator+=(const mint& rhs){_v += rhs._v;if(_v >= umod()) _v -= umod();return *this;}mint& operator-=(const mint& rhs){_v += mod() - rhs._v;if(_v >= umod()) _v -= umod();return *this;}mint& operator*=(const mint& rhs){_v = bt.mul(_v, rhs._v);return *this;}mint& operator/=(const mint& rhs){return *this = *this * rhs.inv();}mint operator+()const{return *this;}mint operator-()const{return mint() - *this;}mint pow(long 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 = inv_gcd(_v, mod());assert(eg.first == 1);return eg.second;}friend mint operator+(const mint& lhs, const mint& rhs){return mint(lhs) += rhs;}friend mint operator-(const mint& lhs, const mint& rhs){return mint(lhs) -= rhs;}friend mint operator*(const mint& lhs, const mint& rhs){return mint(lhs) *= rhs;}friend mint operator/(const mint& lhs, const mint& rhs){return mint(lhs) /= rhs;}friend bool operator==(const mint& lhs, const mint& rhs){return lhs._v == rhs._v;}friend bool operator!=(const mint& lhs, const mint& rhs){return lhs._v != rhs._v;}private:unsigned int _v;static barrett bt;static unsigned int umod(){return bt.umod();}};template <int id>barrett dynamic_modint<id>::bt(998244353);using modint = dynamic_modint<-1>;using modint998244353 = static_modint<998244353>;using modint1000000007 = static_modint<1000000007>;template <class T>using is_modint = std::is_base_of<modint_base, T>;template <class T>using is_modint_t = std::enable_if_t<is_modint<T>::value>;template <class T>using is_static_modint = std::is_base_of<static_modint_base, T>;template <class T>using is_static_modint_t = std::enable_if_t<is_static_modint<T>::value>;template <class> struct is_dynamic_modint : public std::false_type {};template <int id>struct is_dynamic_modint<dynamic_modint<id>> : public std::true_type {};template <class T>using is_dynamic_modint_t = std::enable_if_t<is_dynamic_modint<T>::value>;template<int m>std::ostream &operator<<(std::ostream &dest, const static_modint<m> &a){dest << a.val();return dest;}template<int id>std::ostream &operator<<(std::ostream &dest, const dynamic_modint<id> &a){dest << a.val();return dest;}// 0 <= n < m <= int_max// 前処理 O(n + log(m))// 各種計算 O(1)// 変数 <= ntemplate<typename mint, is_modint<mint>* = nullptr>struct modcomb{private:int n;std::vector<mint> f, i, fi;void init(int _n){assert(0 <= _n && _n < mint::mod());if(_n < f.size()) return;n = _n;f.resize(n + 1), i.resize(n + 1), fi.resize(n + 1);f[0] = fi[0] = mint(1);if(n) f[1] = fi[1] = i[1] = mint(1);for(int j = 2; j <= n; j++) f[j] = f[j - 1] * j;fi[n] = f[n].inv();for(int j = n; j >= 2; j--){fi[j - 1] = fi[j] * j;i[j] = f[j - 1] * fi[j];}}public:modcomb(): n(-1){}modcomb(int _n){init(_n);}void recalc(int _n){init(std::min(mint::mod() - 1, 1 << ceil_pow2(_n)));}mint comb(int a, int b){if((a < 0) || (b < 0) || (a < b)) return 0;return f[a] * fi[a - b] * fi[b];}mint combinv(int a, int b){assert(0 <= b && b <= a);return fi[a] * f[a - b] * f[b];}mint perm(int a, int b){if((a < 0) || (b < 0) || (a < b)) return 0;return f[a] * fi[a - b];}mint perminv(int a, int b){assert(0 <= b && b <= a);return fi[a] * f[a - b];}mint fac(int x){assert(0 <= x && x <= n);return f[x];}mint inv(int x){assert(0 < x && x <= n);return i[x];}mint finv(int x){assert(0 <= x && x <= n);return fi[x];}};template<typename mint, is_modint<mint>* = nullptr>struct modpow_table{std::vector<mint> v;// x^maxkまで計算できるmodpow_table(){}void init(int x, int maxk){v.resize(maxk + 1);v[0] = 1;for(int i = 1; i <= maxk; i++) v[i] = v[i - 1] * x;}mint pow(int k){assert(0 <= k && k < v.size());return v[k];}};using mint = modint998244353;int main(){io_init();int n, m;std::cin >> n >> m;vector<vector<int>> g(n);range(i, 0, m){int a, b;std::cin >> a >> b;a--, b--;if(a < b) swap(a, b);g[a].push_back(b);}vector<mint> tmp(n, 1);lazy_union_find_monoid<range_add_range_sum, mint, mint> uf(tmp);mint ans = 0;range(i, 0, n){mint s = 0;sort(allof(g[i]));//reverse(allof(g[i]));for(int t : g[i]){if(!uf.same(i, t)) s += uf.get(t);uf.unite(i, t);}ans += s + 1;uf.update(i, s + 1);uf.set(i, s + 1);}std::cout << ans << '\n';}