分数: 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
给定的图可能有多边。