恰好一个

题目描述

给定一个具有 $N$ 个顶点和 $M$ 条边的无向图。

顶点称为顶点 $1$、顶点 $2$、……、顶点 $N$,边称为边 $1$、边 $2$、……、边 $M$。边 $i$($1 \le i \le M$)连接顶点 $U_i$ 和顶点 $V_i$。

保证该图是简单图:没有自环,也没有重边。

给图中的每条边定向共有 $2^M$ 种方式。我们希望每个顶点都恰好有一条从该顶点出发指向其他顶点的边。有多少种定向方式满足这个要求?由于答案可能非常大,请对 $998244353$ 取模输出。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

3 3
1 2
1 3
2 3

2

满足条件的定向方式有以下两种:

$1\rightarrow 2$,$2\rightarrow 3$,$1\leftarrow 3$

$1\leftarrow 2$,$2\leftarrow 3$,$1\rightarrow 3$

2 1
1 2

0

显然不可能让每个顶点都恰好有一条边从该顶点出发。

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

4

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le U_i, V_i \le N$
• $U_i \neq V_i$
• 输入中的所有值均为整数。
• 给定的图是简单图。