問題文

$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