F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:鸣谢Vijos,祝Vijos 越办越好! 2:六月月赛题解http://www.lydsy.com/JudgeOnline/upload/sol6.pdf
Problem 3812. -- 主旋律

3812: 主旋律

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 246  Solved: 205
[Submit][Status][Discuss]

Description

响应主旋律的号召,大家决定让这个班级充满爱,现在班级里面有 n 个男生。
如果 a 爱着 b,那么就相当于 a 和 b 之间有一条 a→b 的有向边。如果这 n 个点的图是强联通的,那么就认为这个班级是充满爱的。
不幸的是,有一些不好的事情发生了,现在每一条边都可能被摧毁。我作为爱的使者,想知道有多少种摧毁的方式,使得这个班级任然充满爱呢?(说人话就是有多少边的子集删去之后整个图仍然强联通。)

Input

第一行两个数 n 和 m,表示班级里的男生数和爱的关系数。
接下来 m 行,每行两个数 a 和 b,表示男生 a 爱着男生 b。同时 a 不等于 b。
所有男生从 1 到 n 标号。
同一条边不会出现两遍,但可能出现 a 爱着 b,b 也爱着 a 的情况,这是两条不同的边。

Output

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

Sample 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

Sample Output

9390

HINT

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

Source

2015年国家集训队测试

[Submit][Status][Discuss]

HOME Back