当前没有测试数据。

E - 仅有一个

得分：500分

问题描述

给定一个有$N$个顶点和$M$条边的无向图。 顶点称为顶点$1$，顶点$2$，$\ldots$，顶点$N$，边称为边$1$，边$2$，$\ldots$，边$M$。边$i$ $(1 \leq i \leq M)$连接了顶点$U_i$和顶点$V_i$。 保证该图是简单图：没有自环和重边。

有$2^M$种方法，可以将该图的每条边定向。我们希望每个顶点恰有一条从该顶点指向另一个顶点的边。有多少种方法可以定向边以满足这个要求？由于答案可能很大，将其模$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$

输出

打印答案。

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

有4种方法可以定向边以满足要求：