当前没有测试数据。

题目大意

给定一个有$N$个顶点、$N-1+M$条有向边的图，顶点和边均有编号。其中$1 \le i \le M$的边$i$是从顶点$X_i$指向$Y_i$的有向边，$1 \le i \le N-1$的边$M+i$是从顶点$i+1$指向顶点$i$的有向边。

从前$M$条边中选择若干条（可以选0条）进行删除，总共有$2^M$种选择方式。需要求出删除所选边后，图仍为强连通的选择方式数量，答案对$998244353$取模。

输入格式

第一行输入两个整数$N$和$M$ 接下来$M$行，每行输入两个整数$X_i$和$Y_i$，表示第$i$条边是从$X_i$指向$Y_i$的有向边

输出格式

输出满足条件的选择方式数量，答案对$998244353$取模

数据范围

$2 \le N \le 2 \times 10^5$ $1 \le M \le 2 \times 10^5$ $1 \le X_i < Y_i \le N$ 所有输入均为整数，图中可能存在多重边

样例输入1

4 3
1 4
1 3
2 4

样例输出1

5

样例说明1

选择删除的边的编号集合为$\{\}$、$\{1\}$、$\{2\}$、$\{3\}$、$\{2,3\}$时，图保持强连通，共5种合法方式。

样例输入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

来源

AtCoder ABC450 F题 https://atcoder.jp/contests/abc450/tasks/abc450_f