#P11714. [清华集训 2014] 主旋律
[清华集训 2014] 主旋律
题目描述
响应主旋律的号召,大家决定让这个班级充满爱,现在班级里面有 个男生。
如果 爱着 ,那么就相当于 和 之间有一条 的有向边。如果这 个点的图是强联通的,那么就认为这个班级是充满爱的。
不幸的是,有一些不好的事情发生了,现在每一条边都可能被摧毁。我作为爱的使者,想知道有多少种摧毁的方式,使得这个班级任然充满爱呢?(说人话就是有多少边的子集删去之后整个图仍然强联通。)
输入格式
第一行两个数 和 ,表示班级里的男生数和爱的关系数。
接下来 行,每行两个数 和 ,表示男生 爱着男生 。同时 不等于 。
所有男生从 到 标号。
同一条边不会出现两遍,但可能出现 爱着 , 也爱着 的情况,这是两条不同的边。
输出格式
输出一行一个整数,表示对 取模后的答案。
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
9390
提示
- 对于 20% 的数据满足: ;
- 对于 50% 的数据满足: ;
- 对于 70% 的数据满足: ;
- 对于 100% 的数据满足: 。