#P11714. [清华集训 2014] 主旋律

    ID: 13088 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 7 上传者: 标签>2014容斥原理CTT(清华集训/北大集训)

[清华集训 2014] 主旋律

题目描述

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

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

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

输入格式

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

接下来 mm 行,每行两个数 aabb,表示男生 aa 爱着男生 bb。同时 aa 不等于 bb

所有男生从 11nn 标号。

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

输出格式

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

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% 的数据满足: n5n \leq 5
  • 对于 50% 的数据满足: n8n \leq 8
  • 对于 70% 的数据满足: n10n \leq 10
  • 对于 100% 的数据满足: n15,0mn(n1)n \leq 15, 0 \leq m \leq n(n - 1)