E - Divide Graph Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

N 頂点 M 辺からなる単純連結無向グラフ G が与えられます。 ここで、N\geq 2 です。 頂点には 1 から N までの、辺には 1 から M までの番号がそれぞれ付けられており、辺 i は頂点 U_i と頂点 V_i を結んでいます。 また、各辺には コスト とよばれる値が定められており、辺 i のコストは 2^i です。

あなたは今から、G の連結成分の個数がちょうど 2 になるように、G の辺のうちいくつかを選んで削除します。 （なお、本問題の制約下でこれは必ず達成可能であることが証明できます。）

削除する辺のコストの和としてありうる最小値を 998244353 で割った余りを求めてください。 （998244353 で割った余りを最小化するのではないことに注意してください。）

制約

  • 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
  • i\neq j ならば (U_i, V_i) \neq (U_j, V_j)
  • G は連結
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

出力

削除する辺のコストの和としてありうる最小値を 998244353 で割った余りを出力せよ。

入力例 1

5 7
2 3
1 2
1 5
4 5
2 4
3 5
1 3

出力例 1

22

辺 1,2,4 の 3 本の辺（上図において点線で示されている辺）を削除すると、G の連結成分の個数はちょうど 2 になります。

このとき、削除する辺のコストの和は 2^1+2^2+2^4=22 であり、これが最小です。

入力例 2

2 1
1 2

出力例 2

2

入力例 3

8 16
2 7
5 7
6 8
1 7
4 7
1 3
2 8
5 8
4 8
2 5
3 4
3 8
1 4
1 8
4 6
1 2

出力例 3

54

Score : 475 points

Problem Statement

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.)

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.

Input

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

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

Sample Input 1

5 7
2 3
1 2
1 5
4 5
2 4
3 5
1 3

Sample Output 1

22

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.

Sample Input 2

2 1
1 2

Sample Output 2

2

Sample Input 3

8 16
2 7
5 7
6 8
1 7
4 7
1 3
2 8
5 8
4 8
2 5
3 4
3 8
1 4
1 8
4 6
1 2

Sample Output 3

54