First, the condition that “the number of connected components of \(G\) becomes exactly \(2\)” can be replaced to “\(G\) becomes disconnected.” This condition is strictly looser than the original, but since we are minimizing the total cost of the edges to remove, making the number of connected components three or more is not beneficial, so this replacement does not change the optimal answers.

Next, by considering the edges that we are not removing, the problem can be rephrased as follows:

• You are given a weighted undirected graph \(G\). When you some of the edges of \(G\) so that retaining them (and removing the others) makes \(G\) disconnected, what is the maximum possible total weight of the chosen edges?

Note that the answer to the original problem is obtained by subtracting the answer to above from \(\sum_{i=1}^{N} 2^i\).

While this problem is not easy in general, in our case edge \(i\) has weight \(2^i\), which justifies the following greedy algorithm:

• Let \(G\) initially have no edges. For \(i=M,M-1,\dots,1\), do the following:
  • Add edge \(i\) to \(G\) if and only if adding it does not make \(G\) connected. If the edge is added, add \(2^i\) to the answer.

Proof

Since the solution obtained by the greedy algorithm above obviously satisfies the condition, it suffices to show that it is optimal. Suppose that the result is not optimal. Fix an optimal solution, and let \(A\) be the set of indices of edges chosen by the optimal solution, and \(B\) be that of the greedy algorithm. By assumption \(A\neq B\), so we can take the maximum integer \(x\) that is contained in exactly one of \(A\) and \(B\). If \(x\in A \land x\notin B\), the edge set obtained by adding edge \(x\) in the step \(i=x\) of the greedy algorithm is a subset of \(A\), which is disconnected, but \(x\notin B\) implies edge \(x\) is not chosen in the greedy algorithm; contradiction. Meanwhile, if \(x\in B\land x\notin A\), then \(\sum_{i \in A\land i\leq x} 2^i \leq 2^1+2^2+\cdots +2^{x-1} < 2^x \leq \sum_{i \in B\land i\leq x} 2^i \), so the total edge weight is larger for \(B\), violating the optimality of \(A\). Since both assumptions yield a contradiction, it has been show that the solution obtained by the greedy algorithm is optimal.

Hence, the problem can be solved by simulating this greedy algorithm using a data structure that manages connectivity, such as Disjoint Set Union (DSU).

Sample code (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;
}