题目描述

$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$ で割った余りを出力してください。

输入格式

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

$N$ $M$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_M$ $V_M$

输出格式

答えを出力せよ。

题目大意

给你一个 $N$ 个点 $M$ 条边的无向图，保证没有重边和自环。

要求你给每一条边加附一个方向，使得这张图上的所有点有且只有一条出边。

由于答案可能很大，你只需要输出答案 $\mod 998244353$ 的值。

$N ,M\leq 2\times 10^5$

3 3
1 2
1 3
2 3

2

2 1
1 2

0

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

4

提示

制約

• $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$
• 入力は全て整数である。
• 与えられるグラフは単純である。

Sample Explanation 1

条件をみたす辺の向き付けの方法は、 - $1\rightarrow\ 2$ , $2\rightarrow\ 3$ , $1\leftarrow\ 3$ - $1\leftarrow\ 2$ , $2\leftarrow\ 3$ , $1\rightarrow\ 3$ の $2$ 通りです。

Sample Explanation 2

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