Divide Graph の解説

類題：https://atcoder.jp/contests/abc218/tasks/abc218_e

最初にすべてコストを支払ってしまうことで辺をすべて削除させ、その後に辺を追加できるところは追加することでコストを減らしていく。

最小全域木じゃないから辺の大きい方からコストとっていくので本当に大丈夫かな？とも一瞬思ったがbitで考えて桁の高い箇所から減らしていくのが最適だからこれでいい。

辺を追加できるところとは、連結成分が2未満にならない辺。

fn main() {
    input! {
        n: usize,
        m: usize,
        uv: [(Usize1, Usize1); m]
    }
    let mut ans = {
        let mut ans = ModInt998244353::new(0);
        for i in 0..m {
            ans += ModInt998244353::new(2).pow(i as u64 + 1);
        }
        ans
    };

    let mut uf = Dsu::new(n);
    let mut count = n;
    for i in (0..m).rev() {
        let (u, v) = uv[i];
        let same = uf.same(u, v);
        if same {
            ans -= ModInt998244353::new(2).pow(i as u64 + 1);
            continue;
        }
        if count == 2 {
            continue;
        }
        uf.merge(u, v);
        count -= 1usize;
        ans -= ModInt998244353::new(2).pow(i as u64 + 1);
    }
    println!("{}", ans);
}