""" 連結成分ごとに場合の数を持っておけばいい? 違うな… dp[v] = vで終わっているrecordの数 dp2[v] = 頂点vに居るときのrecordの数 新しい頂点vを追加する時… 繋がっている連結成分の頂点uに関して、u以上で終わっているrecordの数の合計を出せばok? mergeと全体加算? ------提出後更新------ 4 4 1 3 3 2 1 4 2 4 がだめでした 大きい方じゃなくて、小さい方の和を持っておくといける? ??? もしかして部分永続ufが必要ですか?? """ import sys from sys import stdin def uf_find(n,p): ufl = [] while p[n] != n: ufl.append(n) n = p[n] for i in ufl: p[i] = n return n def uf_union(a,b): ap = uf_find(a,p) bp = uf_find(b,p) if ap == bp: return True else: #print (dp2,"start",foot) if size[ap] > size[bp]: p[bp] = ap size[ap] += size[bp] for v in rev[bp]: rev[ap].add(v) dp2[v] = (dp2[v] + foot[bp] - foot[ap]) % mod else: p[ap] = bp size[bp] += size[ap] for v in rev[ap]: rev[bp].add(v) dp2[v] = (dp2[v] + foot[ap] - foot[bp]) % mod #print (dp2,"end",foot) #part_max[ap] = part_max[bp] = max(part_max[ap] = part_max[bp]) return False N,M = map(int,stdin.readline().split()) lis = [ [] for i in range(N) ] for i in range(M): u,v = map(int,stdin.readline().split()) u -= 1 v -= 1 lis[u].append(v) lis[v].append(u) p = [i for i in range(N)] size = [1] * N rev = [ set([i]) for i in range(N) ] #part_max = [i for i in range(N)] dp = [1] * N dp2 = [0] * N foot = [0] * N mod = 998244353 for v in range(N): p2u = {} for u in lis[v]: if u < v: p_of_u = uf_find(u,p) if p_of_u not in p2u: p2u[p_of_u] = u p2u[p_of_u] = min(p2u[p_of_u] , u) for p_of_u in p2u: dp[v] += dp2[p2u[p_of_u]] + foot[p_of_u] dp[v] %= mod # merge for u in lis[v]: if u < v: vp = uf_find(u,p) up = uf_find(v,p) if vp != up: uf_union(up,vp) allp = uf_find(v,p) foot[allp] += dp[v] foot[allp] %= mod #print (dp,dp2,foot,rev) for i in range(N): ip = uf_find(i,p) #print (i+1,(dp2[i] + foot[ip]) % mod) print (sum(dp) % mod)