AT_abc447_e [ABC447E] Divide Graph

You are given a simple connected undirected graph $ G $ with $ N $ vertices and $ M $ edges. Here, $ N \geq 2 $ . The vertices are numbered $ 1 $ to $ N $ , and the edges are numbered $ 1 $ to $ M $ ; edge $ i $ connects vertices $ U_i $ and $ V_i $ . Each edge has a value called a **cost**, and the cost of edge $ i $ is $ 2^i $ . You will now choose some edges of $ G $ to delete so that the number of connected components of $ G $ becomes exactly $ 2 $ . (It can be proved that this is always achievable under the constraints of this problem.) Find the minimum possible sum of costs of the deleted edges, modulo $ 998244353 $ . (Note that you are not minimizing the remainder modulo $ 998244353 $ .)

The input is given from Standard Input in the following format: > $N$ $M$ > > $U_1$ $V_1$ > > $U_2$ $V_2$ > > $\vdots$ > > $U_M$ $V_M$

Output the minimum possible sum of costs of the deleted edges, modulo $ 998244353 $ .

### Sample Explanation 1  Deleting edges $ 1, 2, 4 $ (the edges shown as dashed lines in the figure above) makes the number of connected components of $ G $ exactly $ 2 $ . In this case, the sum of costs of the deleted edges is $ 2^1+2^2+2^4=22 $ , which is the minimum. ### Constraints - $ 2 \leq N \leq 2\times 10^5 $ - $ N-1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right) $ - $ 1 \leq U_i < V_i \leq N $ - $ (U_i, V_i) \neq (U_j, V_j) $ if $ i \neq j $ - $ G $ is connected. - All input values are integers.