Just one

题目描述

给出一个无向图，包含 $N$ 个顶点和 $M$ 条边。 顶点被称为 顶点 $1$、顶点 $2$、$\ldots$、顶点 $N$，边被称为 边 $1$、边 $2$、$\ldots$、边 $M$。边 $i$ $(1 \leq i \leq 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

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$ 输入中的所有值均为整数。 给定的图是简单图。存在两种将边指向以达到目标的方法：

$1\rightarrow 2$ , $2\rightarrow 3$ , $1\leftarrow 3$ $1\leftarrow 2$ , $2\leftarrow 3$ , $1\rightarrow 3$
显然不可能使每个顶点都有一条边从该顶点出发。

标签: AtCoder|abc226E

来源

AtCoder|abc226E