QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100

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

统计

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

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

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

求在 $ 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} $