E - Just one Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点 M 辺の無向グラフが与えられます。 頂点は頂点 1 ,頂点 2 , \ldots ,頂点 N、辺は辺 1 ,辺 2 , \ldots ,辺 M と番号付けられており、特に辺 i (1 \leq i \leq M) は頂点 U_i と頂点 V_i を結んでいます。 また、このグラフは単純であることが保証されます。すなわち、自己ループや多重辺は存在しません。

このグラフの M 本の辺すべてに向き付けをする方法は 2^M 通り考えられますが、 そのうち、どの頂点についても、その頂点から他の頂点に向かう辺がちょうど 1 本ずつ存在するような向き付けの方法は何通りありますか。 答えは非常に大きくなる可能性があるので、998244353 で割った余りを出力してください。

制約

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq U_i,V_i \leq N
  • U_i \neq V_i
  • 入力は全て整数である。
  • 与えられるグラフは単純である。

入力

入力は以下の形式で標準入力から与えられる。

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

出力

答えを出力せよ。

入力例 1

3 3
1 2
1 3
2 3

出力例 1

2

条件をみたす辺の向き付けの方法は、

  • 1\rightarrow 2 , 2\rightarrow 3 , 1\leftarrow 3
  • 1\leftarrow 2 , 2\leftarrow 3 , 1\rightarrow 3

の 2 通りです。

入力例 2

2 1
1 2

出力例 2

0

すべての頂点から 1 本ずつ辺が出ているようにすることは明らかに不可能です。

入力例 3

7 7
1 2
2 3
3 4
4 2
5 6
6 7
7 5

出力例 3

4

Score : 500 points

Problem Statement

Given is an undirected graph with N vertices and M edges. The vertices are called Vertex 1, Vertex 2, \ldots, Vertex N, and the edges are called Edge 1, Edge 2, \ldots, Edge M. Edge i (1 \leq i \leq M) connects Vertex U_i and Vertex V_i. It is guaranteed that the graph is simple: it has no self-loops and no multi-edges.

There are 2^M ways to direct every edge in this graph. We want each vertex to have exactly one edge going from that vertex to another vertex. How many ways are there to direct the edges in that way? Since the answer may be enormous, print it modulo 998244353.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq M \leq 2\times 10^5
  • 1 \leq U_i,V_i \leq N
  • U_i \neq V_i
  • All values in input are integers.
  • The given graph is simple.

Input

Input is given from Standard Input in the following format:

N M
U_1 V_1
U_2 V_2
\vdots
U_M V_M

Output

Print the answer.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

There are two ways to direct the edges to achieve the objective:

  • 1\rightarrow 2 , 2\rightarrow 3 , 1\leftarrow 3
  • 1\leftarrow 2 , 2\leftarrow 3 , 1\rightarrow 3

Sample Input 2

2 1
1 2

Sample Output 2

0

It is obviously impossible to make every vertex have one edge going from that vertex.

Sample Input 3

7 7
1 2
2 3
3 4
4 2
5 6
6 7
7 5

Sample Output 3

4