AT_abc450_f.[ABC450F] Strongly Connected 2

有一个有向图，包含 $N$ 个顶点和 $N-1+M$ 条边，其中边和顶点均从 1 开始编号。
对于 $1 \leq i \leq M$，第 $i$ 条边是从顶点 $X_i$ 指向顶点 $Y_i$ 的有向边；对于 $1 \leq i \leq N-1$，第 $M+i$ 条边是从顶点 $i+1$ 指向顶点 $i$ 的有向边。

从 $1,2,\dots, M$ 这 $M$ 条边中任选一些（可以不选），共有 $2^M$ 种选择方式。对于每一种选择方式，如果从图中删除选中的边后，图依然是强连通的，请问这样的选择方式有多少种？请输出方案数对 $998244353$ 取模后的结果。

输入从标准输入读入，格式如下：

$N$ $M$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$

输出答案。

样例解释 1

当选中的边编号集合为 $\{\}, \{1\}, \{2\}, \{3\}, \{2,3\}$ 时，删除这些边后图仍然为强连通，总共有五种方式。

样例解释 2

给定的有向图可能包含重边。

数据范围

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

由 ChatGPT 5 翻译