まず、「\(G\) の連結成分の個数がちょうど \(2\) になる」という条件は、「\(G\) が非連結になる」という条件に変えることができます。これは元の条件よりも真に緩い条件ですが、削除する辺のコストの総和を最小化するという目的下において、連結成分の個数を \(3\) 以上にすることを許しても得することはなく、故に最適解が変化しないからです。

続いて、削除せず残す辺の方に着目することで、本問題を以下のように言い換えることができます。

• 重み付き無向グラフ \(G\) が与えられる。\(G\) の辺のうちいくつかの辺を選ぶ。選んだ辺のみを残したとき \(G\) が連結に ならない という条件のもと、選ぶ辺の重みの総和を最大でいくつにできるか？

なお、元の問題の答えは \(\sum_{i=1}^{N} 2^i\) からこの問題の答えを引いたものになります。

一般にはこの問題は簡単ではありませんが、本問題では辺 \(i\) の重みが \(2^i\) という特殊な形で表されることから、以下のような単純な貪欲法が正当になります。

• \(G\) に全く辺がない状態から始めて、\(i=M,M-1,\dots,1\) の順に以下を行う：
  • \(G\) に辺 \(i\) を追加しても \(G\) が連結にならない場合、またその場合に限り、\(G\) に辺 \(i\) を追加し、答えに \(2^i\) を加算する。

よって、Union-Find などの連結性を管理するデータ構造を用いてこの貪欲法をシミュレーションすることで、本問題を解くことができます。

実装例 (C++) :

#include <bits/stdc++.h>
#include <atcoder/dsu>
#include <atcoder/modint>

using namespace std;

using mint = atcoder::modint998244353;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> u(m), v(m);
    vector<mint> cost(m);
    for (int i = 0; i < m; i++) {
        cin >> u[i] >> v[i];
        --u[i], --v[i];
        cost[i] = (i ? cost[i - 1] * 2 : 2);
    }

    atcoder::dsu uf(n);
    mint ans = 0;
    int cnt = n;
    for (int i = m - 1; i >= 0; i--) {
        if (!uf.same(u[i], v[i])) {
            if (cnt > 2) {
                uf.merge(u[i], v[i]);
                --cnt;
            } else {
                ans += cost[i];
            }
        }
    }
    cout << ans.val() << endl;
}