

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