QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+13]

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

Statistics

给定一张 n 个点 m 条边的无向图。图无重边无自环,且保证连通。

对于一条连接两个点 (a,b) 的边,定义它代表的区间为 (min(左开右开区间)。

定义一张图是好的,当且仅当任意两条边代表的区间相互包含或互不相交。

求在 n! 种给点重标号的方案中,有多少种使得最后得到的图是好的。

答案对 10^9+7 取模。

输入格式

第一行两个正整数 n m ,表示图的点数与边数。

接下来 m 行,每行两个数 u_i v_i ,表示第 i 条边连接重标号前的节点 u_i v_i

输出格式

输出一行一个正整数,表示答案对 10^9+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 \leq n,m \leq 2 \times 10^5

子任务编号 n\leq m\leq 特殊性质分值
1 10 30 5
2 2\times10^5 n-1 5
3 2\times10^5 n 5
4 300 1000 重标号前的图是好的 20
5 300 1000 保证答案取模后不为 0 20
6 300 1000 m=2n-3 20
7 300 1000 10
8 2\times10^5 2\times10^5 15

时间限制: 2\texttt{s}

空间限制: 512\texttt{MB}