给定一张 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}