#P13807. [diverta2019]Edge Ordering

    ID: 13008 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2700省选/NOI-子集 DPSOS DP计数 DP贡献法阶乘逆元预处理

[diverta2019]Edge Ordering

题目描述

给定一个包含 NN 个顶点和 MM 条边的简单连通无向图 GG。顶点编号为 11 到 NN,边编号为 11 到 MM。

第 ii 条边是连接顶点 aia_i 和 bib_i 的无向边。保证由顶点 1,2,…,N1,2,\ldots,N 和边 1,2,…,N−11,2,\ldots,N-1 构成的子图是 GG 的一棵生成树。

如果对边赋予权值,使得由顶点 1,2,…,N1,2,\ldots,N 和边 1,2,…,N−11,2,\ldots,N-1 构成的树成为 GG 的最小生成树,则称这样的权值分配为“良好分配”。

每条边都要被分配一个 11 到 MM 的互不相同的整数权值。这样的分配方式共有 M!M! 种。在所有良好分配中,计算最小生成树中包含的边的权值之和,并将这些和的总和对 109+710^9+7 取模后输出。

输入格式

输入以如下格式从标准输入读入:

NN MM
a1a_1 b1b_1
⋮\vdots
aMa_M bMb_M

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 3
1 2
2 3
1 3

输出 #1

6

输入输出样例 #2

输入 #2

4 4
1 2
3 2
3 4
1 3

输出 #2

50

输入输出样例 #3

输入 #3

15 28
10 7
5 9
2 13
2 14
6 1
5 12
2 10
3 9
10 15
11 12
12 6
2 12
12 8
4 10
15 3
13 14
1 15
15 12
4 14
1 7
5 11
7 13
9 10
2 7
1 9
5 6
12 14
5 2

输出 #3

657573092

说明/提示

限制条件

  • 所有输入均为整数。
  • 2≤N≤202 \leq N \leq 20
  • N−1≤M≤N(N−1)2N-1 \leq M \leq \frac{N(N-1)}{2}
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • 图 GG 中不存在自环或重边。
  • 由顶点 1,2,…,N1,2,\ldots,N 和边 1,2,…,N−11,2,\ldots,N-1 构成的子图是 GG 的一棵生成树。

样例解释 1

  • 只有当第 33 条边被分配权值 33 时,才是良好分配。
  • 在这些良好分配中,最小生成树中包含的边的权值之和为 33,良好分配的数量为 22,因此答案为 66。

样例解释 3

  • 请将总和对 109+710^9+7 取模后输出。