Submission #73713117

---

Source Code Expand

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353;

int n, m;
int cnt[26];
int u[N], v[N];
int fa[N];

int find(int p){
    return p == fa[p] ? p : fa[p] = find(fa[p]);
}

void merge(int x, int y){
    fa[find(x)] = find(y);
}

int __pow[N];

void init(){
    __pow[0] = 1;
    for(int i=1;i<N;i++){
        __pow[i] = (__pow[i-1] << 1) % 998244353;
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    init();
    cin >> n >> m;
    int tot = 0;
    for(int i=1;i<=m;i++){
        cin >> u[i] >> v[i];
        tot = (tot + __pow[i]) % mod;
    }
    int cnt = n, ans = 0;
    for(int i=1;i<=n;i++) fa[i] = i;
    for(int i=m;i>=1;i--){
        if(find(u[i]) != find(v[i])){
            if(cnt == 2) continue;
            merge(u[i], v[i]);
            cnt --;
            ans = (ans + __pow[i]) % 998244353;
        }else{
            ans = (ans + __pow[i]) % 998244353;
        }
    }
    cout << (tot - ans + mod) % mod;
    return 0;
}

Submission Info

Judge Result