← 返回题目列表

AtCoder · abc450_f

F. 强连接2

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

分数: 525 点

问题陈述

有一个有向图 N 顶点和 N-1+M 边,边和顶点已编号。
对于 1 \leq i \leq M,边缘 i 是从顶点开始的有向边 X_i 到顶点 Y_i,并且对于 1 \leq i \leq N-1,边缘 M+i 是从顶点开始的有向边 i+1 到顶点 i.

有 2^M 从边中选择一些(可能是零)边的方法 1, 2, \dots, M。在这些方法中,有多少种会导致删除所选边后图强连通?求计数模数 998244353.

约束

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq X_i < Y_i \leq N
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

输出

输出答案。


示例输入 1

4 3
1 4
1 3
2 4

示例输出 1

5

当所选边索引集是以下之一时,该图是强连接的: \{\}, \{1\}, \{2\}, \{3\}, \{2,3\},给出了五种方法。


示例输入 2

10 11
1 4
1 4
3 9
2 5
3 4
9 10
6 9
4 10
1 3
8 10
4 7

示例输出 2

1297

给定的图可能有多边。