F - Strongly Connected 2 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 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 への有向辺です。

辺 1,2,\dots,M のうちいくつか( 0 個でもよい) の辺を選ぶ方法は 2^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\} の 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

与えられるグラフは多重辺を持つことがあります。

Score : 525 points

Problem Statement

There is a directed graph with N vertices and N-1+M edges, with edges and vertices numbered.
For 1 \leq i \leq M, edge i is a directed edge from vertex X_i to vertex Y_i, and for 1 \leq i \leq N-1, edge M+i is a directed edge from vertex i+1 to vertex i.

There are 2^M ways to choose some (possibly zero) edges from among edges 1, 2, \dots, M. Among these ways, how many result in the graph being strongly connected after deleting the chosen edges? Find the count modulo 998244353.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq X_i < Y_i \leq N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

Output

Output the answer.

Sample Input 1

4 3
1 4
1 3
2 4

Sample Output 1

5

The graph is strongly connected when the set of chosen edge indices is one of \{\}, \{1\}, \{2\}, \{3\}, \{2,3\}, giving five ways.

Sample Input 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

Sample Output 2

1297

The given graph may have multi-edges.