样例下载

题目描述

有一个无向图，含有 N 个点，M 条边。现在要给每条边添加方向，使得无向图变成有向图。规则如下：

（1）一条边只能添加一个方向。

（2）任意一个点的入度不能超过 1.

求：可以得到多少个不同的有向图？答案可能很大，你需要输出其 mod 1,000,000,007 的值。

注：两个有向图不同，当前仅当存在一条边添加的方向不同。

输入格式

第一行：两个整数 N、M

接下来 M 行，每行两个整数 u、v，表示一条边的两个端点 (1 ≤ u, v ≤ N, u ≠ v)。可能相同的两个点之间有多条边。

输出格式

一个整数，表示答案。

样例输入1

5 4 
1 2 
3 2 
4 5 
4 5

样例输出1

6

样例输入2

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

样例输出2

0

数据范围

1 ≤ N, M ≤ 100,000