201535: [AtCoder]ARC153 F - Tri-Colored Paths

Memory Limit：1024 MB Time Limit：2 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

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

Input

题意翻译

给出一张 $N$ 个点 $M$ 条边的简单无向连通图。 你可以将分别每一条边染为 $1,2,3$ 三种颜色之一。问不同的染色方案数，使得图中存在一条路径，其上同时存在三种颜色的边。答案对 $998244353$ 取模。

Source/Category

加入题单

算法标签：