UOJ Logo Universal Online Judge

UOJ

#37. 【清华集训2014】主旋律

统计

响应主旋律的号召,大家决定让这个班级充满爱,现在班级里面有 $n$ 个男生。

如果 $a$ 爱着 $b$,那么就相当于 $a$ 和 $b$ 之间有一条 $a \rightarrow b$ 的有向边。如果这 $n$ 个点的图是强联通的,那么就认为这个班级是充满爱的。

不幸的是,有一些不好的事情发生了,现在每一条边都可能被摧毁。我作为爱的使者,想知道有多少种摧毁的方式,使得这个班级任然充满爱呢?(说人话就是有多少边的子集删去之后整个图仍然强联通。)

输入格式

第一行两个数 $n$ 和 $m$,表示班级里的男生数和爱的关系数。

接下来 $m$ 行,每行两个数 $a$ 和 $b$,表示男生 $a$ 爱着男生 $b$。同时 $a$ 不等于 $b$。

所有男生从 $1$ 到 $n$ 标号。

同一条边不会出现两遍,但可能出现 $a$ 爱着 $b$,$b$ 也爱着 $a$ 的情况,这是两条不同的边。

输出格式

输出一行一个整数,表示对 $10^9 + 7$ 取模后的答案。

样例一

input

5 15
4 3
4 2
2 5
2 1
1 2
5 1
3 2
4 1
1 4
5 4
3 4
5 3
2 3
1 5
3 1

output

9390

限制与约定

对于 20% 的数据满足: $n \leq 5$;

对于 50% 的数据满足: $n \leq 8$;

对于 70% 的数据满足: $n \leq 10$;

对于 100% 的数据满足: $n \leq 15, 0 \leq m \leq n(n − 1)$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

来源

中国国家队清华集训2014~2015 Day 1 - By 陈立杰

下载

样例数据下载