#line 1 "library/Template/template.hpp" #include using namespace std; #define rep(i,a,b) for(int i=(int)(a);i<(int)(b);i++) #define ALL(v) (v).begin(),(v).end() #define UNIQUE(v) sort(ALL(v)),(v).erase(unique(ALL(v)),(v).end()) #define SZ(v) (int)v.size() #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(v,x) int(lower_bound(ALL(v),(x))-(v).begin()) #define UB(v,x) int(upper_bound(ALL(v),(x))-(v).begin()) using ll=long long int; using ull=unsigned long long; const int inf = 0x3fffffff; const ll INF = 0x1fffffffffffffff; templateinline bool chmax(T& a,T b){if(ainline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;} templateT ceil(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?(x+y-1)/y:x/y);} templateT floor(T x,U y){assert(y!=0); if(y<0)x=-x,y=-y; return (x>0?x/y:(x-y+1)/y);} templateint popcnt(T x){return __builtin_popcountll(x);} templateint topbit(T x){return (x==0?-1:63-__builtin_clzll(x));} templateint lowbit(T x){return (x==0?-1:__builtin_ctzll(x));} #line 2 "library/Utility/fastio.hpp" #include class FastIO{ static constexpr int L=1<<16; char rdbuf[L]; int rdLeft=0,rdRight=0; inline void reload(){ int len=rdRight-rdLeft; memmove(rdbuf,rdbuf+rdLeft,len); rdLeft=0,rdRight=len; rdRight+=fread(rdbuf+len,1,L-len,stdin); } inline bool skip(){ for(;;){ while(rdLeft!=rdRight and rdbuf[rdLeft]<=' ')rdLeft++; if(rdLeft==rdRight){ reload(); if(rdLeft==rdRight)return false; } else break; } return true; } template::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdLeft=rdRight)reload(); x=0; while(rdbuf[rdLeft]>='0' and rdLeft::value,int> =0>inline bool _read(T& x){ if(!skip())return false; if(rdLeft+20>=rdRight)reload(); bool neg=false; if(rdbuf[rdLeft]=='-'){ neg=true; rdLeft++; } x=0; while(rdbuf[rdLeft]>='0' and rdbuf[rdLeft]<='9' and rdLeft='0' and rdbuf[rdLeft]<='9' and rdLeft=rdRight)reload(); x=rdbuf[rdLeft++]; return true; } inline bool _read(string& x){ if(!skip())return false; for(;;){ int pos=rdLeft; while(pos' ')pos++; x.append(rdbuf+rdLeft,pos-rdLeft); if(rdLeft==pos)break; rdLeft=pos; if(rdLeft==rdRight)reload(); else break; } return true; } templateinline bool _read(vector& v){ for(auto& x:v){ if(!_read(x))return false; } return true; } char wtbuf[L],tmp[50]; int wtRight=0; inline void _write(const char& x){ if(wtRight>L-32)flush(); wtbuf[wtRight++]=x; } inline void _write(const string& x){ for(auto& c:x)_write(c); } template::value,int> =0>inline void _write(T x){ if(wtRight>L-32)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); if (__builtin_expect(x == std::numeric_limits::min(), 0)) { switch (sizeof(x)) { case 2: _write("32768"); return; case 4: _write("2147483648"); return; case 8: _write("9223372036854775808"); return; } } x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(__int128_t x){ if(wtRight>L-40)flush(); if(x==0){ _write('0'); return; } else if(x<0){ _write('-'); x=-x; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(__uint128_t x){ if(wtRight>L-40)flush(); if(x==0){ _write('0'); return; } int pos=0; while(x!=0){ tmp[pos++]=char((x%10)|48); x/=10; } rep(i,0,pos)wtbuf[wtRight+i]=tmp[pos-1-i]; wtRight+=pos; } inline void _write(double x){ ostringstream oss; oss << fixed << setprecision(15) << double(x); string s = oss.str(); _write(s); } templateinline void _write(const vector& v){ rep(i,0,v.size()){ if(i)_write(' '); _write(v[i]); } } public: FastIO(){} ~FastIO(){flush();} inline void read(){} template inline void read(Head& head,Tail&... tail){ assert(_read(head)); read(tail...); } templateinline void write(){if(ln)_write('\n');} template inline void write(const Head& head,const Tail&... tail){ _write(head); write(tail...); if(space)_write(' '); } inline void flush(){ fwrite(wtbuf,1,wtRight,stdout); wtRight=0; } }; /** * @brief Fast IO */ #line 3 "sol.cpp" #line 2 "library/Math/modint.hpp" template struct fp { int v; static constexpr int get_mod() { return mod; } int inv() const { int tmp, a = v, b = mod, x = 1, y = 0; while (b) tmp = a / b, a -= tmp * b, swap(a, b), x -= tmp * y, swap(x, y); if (x < 0) { x += mod; } return x; } fp(ll x = 0) : v(x >= 0 ? x % mod : (mod - (-x) % mod) % mod) {} fp operator-() const { return fp() - *this; } fp pow(ll t) { assert(t >= 0); fp res = 1, b = *this; while (t) { if (t & 1) res *= b; b *= b; t >>= 1; } return res; } fp &operator+=(const fp &x) { if ((v += x.v) >= mod) v -= mod; return *this; } fp &operator-=(const fp &x) { if ((v += mod - x.v) >= mod) v -= mod; return *this; } fp &operator*=(const fp &x) { v = ll(v) * x.v % mod; return *this; } fp &operator/=(const fp &x) { v = ll(v) * x.inv() % mod; return *this; } fp operator+(const fp &x) const { return fp(*this) += x; } fp operator-(const fp &x) const { return fp(*this) -= x; } fp operator*(const fp &x) const { return fp(*this) *= x; } fp operator/(const fp &x) const { return fp(*this) /= x; } bool operator==(const fp &x) const { return v == x.v; } bool operator!=(const fp &x) const { return v != x.v; } friend istream &operator>>(istream &is, fp &x) { return is >> x.v; } friend ostream &operator<<(ostream &os, const fp &x) { return os << x.v; } }; template T Inv(ll n) { static const int md = T::get_mod(); static vector buf({0, 1}); assert(n > 0); n %= md; while (SZ(buf) <= n) { int k = SZ(buf), q = (md + k - 1) / k; buf.push_back(buf[k * q - md] * q); } return buf[n]; } template T Fact(ll n, bool inv = 0) { static const int md = T::get_mod(); static vector buf({1, 1}), ibuf({1, 1}); assert(n >= 0 and n < md); while (SZ(buf) <= n) { buf.push_back(buf.back() * SZ(buf)); ibuf.push_back(ibuf.back() * Inv(SZ(ibuf))); } return inv ? ibuf[n] : buf[n]; } template T nPr(int n, int r, bool inv = 0) { if (n < 0 || n < r || r < 0) return 0; return Fact(n, inv) * Fact(n - r, inv ^ 1); } template T nCr(int n, int r, bool inv = 0) { if (n < 0 || n < r || r < 0) return 0; return Fact(n, inv) * Fact(r, inv ^ 1) * Fact(n - r, inv ^ 1); } template T nHr(int n, int r, bool inv = 0) { return nCr(n + r - 1, r, inv); } /** * @brief Modint */ #line 5 "sol.cpp" using Fp = fp<998244353>; #line 2 "library/DataStructure/bit.hpp" templatestruct BIT{ int n; T all=0; vector val; BIT(int _n=0):n(_n),val(_n+10){} void clear(){val.assign(n+10,0); all=T();} void add(int i,T x){ for(i++;i<=n;i+=(i&-i))val[i]=val[i]+x; all+=x; } T sum(int i){ T res=0; for(;i;i-=(i&-i))res+=val[i]; return res; } T sum(int L,int R){return sum(R)-sum(L);} // [L,R) int lower_bound(T x){ int ret=0,len=1; while(2*len<=n)len<<=1; for(;len>=1;len>>=1){ if(ret+len<=n and val[ret+len]; vector> g; vector sz,in,out,rev,hs,par,dist; void dfs(int v,int p){ par[v]=p; sz[v]=1; if(p!=-1)dist[v]=dist[p]+1; if(!g[v].empty() and g[v][0]==p)swap(g[v][0],g[v].back()); for(auto& to:g[v])if(to!=p){ dfs(to,v); sz[v]+=sz[to]; if(sz[g[v][0]]in[v])swap(u,v); if(hs[u]==hs[v])return u; } } vector

get(int u,int p,bool es=0){ assert(in[p]<=in[u] and out[u]<=out[p]); vector

res; while(hs[u]!=hs[p]){ res.push_back({in[hs[u]],in[u]+1}); u=par[hs[u]]; } res.push_back({in[p]+es,in[u]+1}); return res; } int jump(int u,int v,int k){ if(k<0)return -1; int g=lca(u,v); int d0=dist[u]+dist[v]-dist[g]*2; if(d0=in[to])return rev[in[st]-k]; k-=in[st]-in[to]+1; st=par[to]; } } }; /** * @brief Heavy Light Decomposition */ #line 8 "sol.cpp" struct UnionFind { vector par; int n; UnionFind() {} UnionFind(int _n) : par(_n, -1), n(_n) {} int root(int x) { return par[x] < 0 ? x : par[x] = root(par[x]); } bool same(int x, int y) { return root(x) == root(y); } int size(int x) { return -par[root(x)]; } bool unite(int x, int y) { x = root(x), y = root(y); if (x == y) return false; // if(size(x)>size(y))swap(x,y); par[y] += par[x]; par[x] = y; n--; return true; } }; FastIO io; int main() { int n, m; io.read(n, m); vector g(n, vector()); rep(_, 0, m) { int u, v; io.read(u, v); u--; v--; g[v].push_back(u); g[u].push_back(v); } UnionFind uni(n); HLD hld(n); rep(v, 0, n) { for (auto &to : g[v]) if (to < v and !uni.same(to, v)) { hld.add_edge(v, uni.root(to)); uni.unite(to, v); } } hld.run(n - 1); BIT bit(n); using P = pair; rep(v, 0, n) { vector

seg; for (auto &to : g[v]) if (to < v) { auto path = hld.get(to, v, 0); seg.insert(seg.end(), ALL(path)); } sort(ALL(seg)); vector

add; int lb = -1, rb = -1; for (auto &[L, R] : seg) { if (rb < L) { if (lb != -1) add.push_back({lb, rb}); lb = L, rb = R; } else { chmax(rb, R); } } if (lb != -1) add.push_back({lb, rb}); Fp sum = 1; for (auto &[L, R] : add) sum += bit.sum(L, R); bit.add(hld.in[v], sum); } Fp ret = bit.all; io.write(ret.v); return 0; }