#1835. 主旋律

    ID: 1835 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest178来源:qoj.ac数据:公开样例组合数学

主旋律

主旋律

题目描述

全国信息学奥林匹克竞赛 第一试 主旋律 主旋律 【问题描述】 响应主旋律的号召,大家决定让这个班级充满爱,现在班级里面有n 个男生。 如果a 爱着b,那么就相当于a 和b 之间有一条a→b 的有向边。如果这n 个点 的图是强联通的,那么就认为这个班级是充满爱的。 不幸的是,有一些不好的事情发生了,现在每一条边都可能被摧毁。我作为 爱的使者,想知道有多少种摧毁的方式,使得这个班级任然充满爱呢?(说人话 就是有多少边的子集删去之后整个图任然强联通。) 【输入格式】 从文件scon.in 中读入数据。 第一行两个数n 和m,表示班级里的男生数和爱的关系数。 接下来m 行,每行两个数a 和b,表示男生a 爱着男生b。同时a 不等于b。 所有男生从1 到n 标号。 同一条边不会出现两遍,但可能出现a 爱着b,b 也爱着a 的情况,这是两 条不同的边。 【输出格式】 输出到文件scon.out 中。 输出一行一个整数,表示对 109 + 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 第3 页 共6 页 全国信息学奥林匹克竞赛 第一试 主旋律 【样例输出】 9390 【数据规模与约定】 对于 20% 的数据满足: n ≤ 5; 对于 50% 的数据满足: n ≤ 8; 对于 70% 的数据满足: n ≤ 10; 对于 100% 的数据满足: n ≤ 15, 0 ≤ m ≤ n(n − 1)。 第4 页 共6 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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