F - Tri-Colored Paths Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 頂点 M 辺からなる連結かつ単純な無向グラフ G が与えられます．頂点には 1 から N の番号がついており，i 番目の辺は頂点 A_i, B_i を結んでいます．

G の各辺を色 1, 2, 3 のいずれかで塗る方法であって，次の条件を満たすものの個数を 998244353 で割った余りを求めてください．

  • G の単純パスであって，色 1 の辺，色 2 の辺，色 3 の辺のすべてを含むものが存在する．
単純パスとは 単純パスとは，頂点の列 (v_1, \ldots, v_{k+1}) および辺の列 (e_1, \ldots, e_k) の組であって，以下を満たすもののことをいいます．
  • i\neq j \implies v_i\neq v_j
  • 辺 e_i は頂点 v_i と v_{i+1} を結ぶ．

制約

  • 3 \leq N\leq 2\times 10^5
  • 3 \leq M\leq 2\times 10^5
  • 1 \leq A_i, B_i \leq N
  • 与えられるグラフは連結かつ単純である

入力

入力は以下の形式で標準入力から与えられます．

N M
A_1 B_1
\vdots
A_M B_M

出力

G の各辺を色 1, 2, 3 のいずれかで塗る方法であって，問題の条件を満たすものの個数を 998244353 で割った余りを出力してください．

入力例 1

3 3
1 2
1 3
3 2

出力例 1

0

G の単純パスはいずれも辺を 2 つ以下しか含まないので，条件を満たす塗り方は存在しません．

入力例 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

出力例 2

534

入力例 3

6 5
1 3
4 3
5 4
4 2
1 6

出力例 3

144

入力例 4

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

出力例 4

1794

Score : 1000 points

Problem Statement

You are given a simple connected undirected graph G with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertices A_i and B_i.

Find the number of ways to paint each edge of G in color 1, 2, or 3 so that the following condition is satisfied, modulo 998244353.

  • There is a simple path in G that contains an edge in color 1, an edge in color 2, and an edge in color 3.
What is a simple path? A simple path is a pair of a sequence of vertices (v_1, \ldots, v_{k+1}) and a sequence of edges (e_1, \ldots, e_k) that satisfies the following:
  • i\neq j \implies v_i\neq v_j;
  • edge e_i connects vertices v_i and v_{i+1}.

Constraints

  • 3 \leq N\leq 2\times 10^5
  • 3 \leq M\leq 2\times 10^5
  • 1 \leq A_i, B_i \leq N
  • The given graph is simple and connected.

Input

The input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the number of ways to paint each edge of G in color 1, 2, or 3 so that the condition in question is satisfied, modulo 998244353.

Sample Input 1

3 3
1 2
1 3
3 2

Sample Output 1

0

Any simple path in G contains two or fewer edges, so there is no way to satisfy the condition.

Sample Input 2

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Sample Output 2

534

Sample Input 3

6 5
1 3
4 3
5 4
4 2
1 6

Sample Output 3

144

Sample Input 4

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

Sample Output 4

1794