分数: 1000 点
问题陈述
给你一个简单的连通无向图 G 与 N 顶点和 M 边缘。顶点已编号 1 to 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
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