102264: [AtCoder]ABC226 E - Just one

Problem Statement

Given is an undirected graph with $N$ vertices and $M$ edges. The vertices are called Vertex $1$, Vertex $2$, $\ldots$, Vertex $N$, and the edges are called Edge $1$, Edge $2$, $\ldots$, Edge $M$. Edge $i$ $(1 \leq i \leq M)$ connects Vertex $U_i$ and Vertex $V_i$. It is guaranteed that the graph is simple: it has no self-loops and no multi-edges.

There are $2^M$ ways to direct every edge in this graph. We want each vertex to have exactly one edge going from that vertex to another vertex. How many ways are there to direct the edges in that way? Since the answer may be enormous, print it modulo $998244353$.

Constraints

• $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$
• All values in input are integers.
• The given graph is simple.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

2

There are two ways to direct the edges to achieve the objective:

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

Sample Input 2

2 1
1 2

Sample Output 2

0

It is obviously impossible to make every vertex have one edge going from that vertex.

Sample Input 3

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

Sample Output 3

4

问题描述

给定一个包含 N 个顶点和 M 条边的无向图。顶点被称为顶点 1，顶点 2，…，顶点 N，边被称为边 1，边 2，…，边 M。边 i（1≤i≤M）连接顶点 U_i 和顶点 V_i。保证图是简单的：它没有自环和多边形。

有 2^M 种方法来给这个图中的每一条边指定方向。我们希望每个顶点恰好有一条从该顶点到另一个顶点的边。有多少种方法可以以这种方式指定边的方向？由于答案可能非常大，请输出答案模 998244353 的值。

约束

• 2≤N≤2×10^5
• 1≤M≤2×10^5
• 1≤U_i,V_i≤N
• U_i≠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 1
1 2

样例输出 2

0

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

样例输入 3

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

样例输出 3

4