#1806. 这不是一道数据结构题

    ID: 1806 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1434来源:qoj.ac数据:公开样例枚举并查集

这不是一道数据结构题

这不是一道数据结构题

题目描述

标题: 这不是一道数据结构题 - Problem - QOJ.ac

#7854. 这不是一道数据结构题

Statistics

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