还有这么诚实的出题人！

我们最多影响20个点，然后把这20个点的虚树建出来，并且枚举每个点的选举状态，如果一个点选或不选可以通过改\(dp[u][0] = 0\)或\(dp[u][1] = 0\)完成

状态应该不多，因为每条边只有三种选的情况，上限是\(3^{m - n + 1}\)的

然后我们考虑递推出\(dp[u][0]\)和\(dp[u][1]\)在更新它虚树上的父亲的方案数，是可以用\(k_0 * dp[u][0] + k_1 * dp[u][1]\)表示的，这个可以递推出来

然后就剩别把代码敲错了= =

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')#define MAXN 100005#define eps 1e-8//#define ivorysiusing namespace std;typedef long long int64;typedef double db;template
      
       void read(T &res) {    res = 0;char c = getchar();T f = 1;    while(c < '0' || c > '9') {    if(c == '-') f = -1;    c = getchar();    }    while(c >= '0' && c <= '9') {    res = res * 10 + c - '0';    c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {x = -x;putchar('-');}    if(x >= 10) {    out(x / 10);    }    putchar('0' + x % 10);}const int MOD = 998244353;int N,M;struct node {    int to,next;}E[MAXN * 2];int head[MAXN],sumE,belong[MAXN],dfn[MAXN],idx,aux[MAXN],faAux[MAXN],acnt,tot,fa[MAXN][20],dep[MAXN];int sta[MAXN],top,dp[MAXN][2],g[MAXN][2][2],val[MAXN][2],id[MAXN],Ncnt,qa[MAXN][2];pii p[MAXN];int inc(int a,int b) {    return a + b >= MOD ? a + b - MOD : a + b; }int mul(int a,int b) {    return 1LL * a * b % MOD;}int fpow(int x,int c) {    int res = 1,t = x;    while(c) {    if(c & 1) res = mul(res,t);    t = mul(t,t);    c >>= 1;    }    return res;}void update(int &x,int y) {    x = inc(x,y);}int getbl(int x) {    return belong[x] == x ? x : belong[x] = getbl(belong[x]);}void add(int u,int v) {    E[++sumE].to = v;    E[sumE].next = head[u];    head[u] = sumE;}bool cmp(int a,int b) {    return dfn[a] < dfn[b];}int dfs(int u) {    dfn[u] = ++idx;    dep[u] = dep[fa[u][0]] + 1;    dp[u][0] = dp[u][1] = 1;    for(int i = head[u] ; i ; i = E[i].next) {    int v = E[i].to;    if(v != fa[u][0]) {        fa[v][0] = u;        dfs(v);        dp[u][0] = mul(dp[u][0],inc(dp[v][1],dp[v][0]));        dp[u][1] = mul(dp[u][1],dp[v][0]);    }    }}int lca(int u,int v) {    if(dep[u] < dep[v]) swap(u,v);    int l = 18;    while(dep[u] > dep[v]) {    if(dep[fa[u][l]] >= dep[v]) u = fa[u][l];    --l;    }    if(u == v) return u;    l = 18;    while(fa[u][0] != fa[v][0]) {    if(fa[u][l] != fa[v][l]) {        u = fa[u][l];        v = fa[v][l];    }    --l;    }    return fa[u][0];}void build_AuxTree() {    int t = acnt;    top = 0;    for(int i = 1 ; i <= acnt ; ++i) {    if(!top) sta[++top] = aux[i];    else {        int f = lca(aux[i],sta[top]);        while(top >= 1 && dep[sta[top]] > dep[f]) {        if(top == 1 || dep[sta[top - 1]] <= dep[f]) {            faAux[sta[top]] = f;        }        --top;        }        if(sta[top] != f) {        faAux[f] = sta[top];        sta[++top] = f;        aux[++t] = f;        }        sta[++top] = aux[i];        faAux[aux[i]] = f;    }    }    acnt = t;    sort(aux + 1,aux + acnt + 1,cmp);    if(aux[1] != 1) {faAux[aux[1]] = 1;aux[++acnt] = 1;}    sort(aux + 1,aux + acnt + 1,cmp);    for(int i = 1 ; i <= acnt ; ++i) val[aux[i]][0] = dp[aux[i]][0],val[aux[i]][1] = dp[aux[i]][1];    for(int i = acnt ; i >= 2 ; --i) {    int u = aux[i],f = faAux[u];        memset(g[u],0,sizeof(g[u]));    g[u][0][0] = 1;g[u][1][1] = 1;    while(fa[u][0] != f) {        int t = fa[u][0];        val[t][0] = mul(dp[t][0],fpow(inc(dp[u][0],dp[u][1]),MOD - 2));        val[t][1] = mul(dp[t][1],fpow(dp[u][0],MOD - 2));        memset(g[t],0,sizeof(g[t]));        g[t][0][0] = mul( inc( g[u][1][0] , g[u][0][0] ) , val[t][0]);        g[t][0][1] = mul( inc( g[u][1][1] , g[u][0][1] ) , val[t][0]);        g[t][1][0] = mul( g[u][0][0] , val[t][1]);        g[t][1][1] = mul( g[u][0][1] , val[t][1]);              u = t;    }    g[f][0][0] = inc( g[u][1][0] , g[u][0][0] );    g[f][0][1] = inc( g[u][1][1] , g[u][0][1] );    g[f][1][1] = g[u][0][1];    g[f][1][0] = g[u][0][0];    memcpy(g[aux[i]],g[f],sizeof(g[f]));    val[f][0] = mul(val[f][0],fpow(inc(dp[u][0],dp[u][1]),MOD - 2));    val[f][1] = mul(val[f][1],fpow(dp[u][0],MOD - 2));    }}void Init() {    read(N);read(M);    for(int i = 1 ; i <= N ; ++i) belong[i] = i;    int u,v;    for(int i = 1 ; i <= M ; ++i) {    read(u);read(v);    if(getbl(u) != getbl(v)) {        belong[getbl(u)] = getbl(v);        add(u,v);add(v,u);    }    else {        p[++tot] = mp(u,v);    }    }    dfs(1);    if(M == N - 1) {    out(inc(dp[1][0],dp[1][1]));enter;    exit(0);    }    for(int j = 1 ; j <= 18 ; ++j) {    for(int i = 1 ; i <= N ; ++i) {        fa[i][j] = fa[fa[i][j - 1]][j - 1];    }    }    for(int i = 1 ; i <= tot ; ++i) {    aux[++acnt] = p[i].fi;aux[++acnt] = p[i].se;    }    sort(aux + 1,aux + acnt + 1);        acnt = unique(aux + 1,aux + acnt + 1) - aux - 1;    for(int i = 1 ; i <= acnt ; ++i) {    id[aux[i]] = ++Ncnt;    }    sort(aux + 1,aux + acnt + 1,cmp);    build_AuxTree();}int Calc(int S) {    for(int i = 1 ; i <= acnt ; ++i) qa[aux[i]][0] = qa[aux[i]][1] = 1;    for(int i = acnt ; i >= 1 ; --i) {    int u = aux[i];    qa[u][0] = mul( qa[u][0] , val[u][0] );    qa[u][1] = mul( qa[u][1] , val[u][1] );    if(id[u]) {        qa[u][(S >> (id[u] - 1) & 1) ^ 1] = 0;    }    if(u == 1) break;    qa[faAux[u]][0] = mul(inc( mul( g[u][0][1] , qa[u][1] ) , mul( g[u][0][0] , qa[u][0]) )  , qa[faAux[u]][0]);    qa[faAux[u]][1] = mul(inc( mul( g[u][1][1] , qa[u][1] ) , mul( g[u][1][0] , qa[u][0]) )  , qa[faAux[u]][1]);    }    return inc(qa[1][0],qa[1][1]);}void Solve() {    int ans = 0;    for(int S = 0 ; S < (1 << Ncnt) ; ++S) {    bool flag = 1;    for(int i = 1 ; i <= tot ; ++i) {        if((S >> (id[p[i].fi] - 1) & 1) && (S >> (id[p[i].se] - 1) & 1)) {        flag = 0;        break;        }    }    if(!flag) continue;    else update(ans,Calc(S));    }    out(ans);enter;}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Init();    Solve();    return 0;}