#1806. 这不是一道数据结构题
这不是一道数据结构题
这不是一道数据结构题
题目描述
标题: 这不是一道数据结构题 - Problem - QOJ.ac
#7854. 这不是一道数据结构题
The problem was used in the following contests:
给定一张 n 个点 m 条边的无向图。图无重边无自环,且保证连通。
对于一条连接两个点 (a,b) 的边,定义它代表的区间为 (min(a,b),max(a,b))(左开右开区间)。
定义一张图是好的,当且仅当任意两条边代表的区间相互包含或互不相交。
求在 n! 种给点重标号的方案中,有多少种使得最后得到的图是好的。
答案对 109+7 取模。
输入格式
第一行两个正整数 n 和 m,表示图的点数与边数。
接下来 m 行,每行两个数 ui 和 vi,表示第 i 条边连接重标号前的节点 ui 和 vi。
输出格式
输出一行一个正整数,表示答案对 109+7 取模后的结果。
样例一
input
4 5
1 2
1 3
2 3
3 4
2 4
output
8
样例二
input
6 5
1 2
1 3
3 4
3 5
3 6
output
288
样例三
input
4 6
1 2
1 3
1 4
2 3
2 4
3 4
output
0
数据范围
对于 100% 的数据,1≤n,m≤2×105。
子任务编号n≤m≤特殊性质分值11030无522×105n−1无532×105n无543001000重标号前的图是好的2053001000保证答案取模后不为 02063001000m=2n−32073001000无1082×1052×105无15
**时间限制:**2s
**空间限制:**512MB
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 5
1 2
1 3
2 3
3 4
2 4
8
样例 2
6 5
1 2
1 3
3 4
3 5
3 6
288