← 返回题目列表

AtCoder · arc153_f

F. 三色路径

中文机器翻译题面 查看原题

分数: 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