AT_diverta2019_f Edge Ordering

给定一个包含 $N$ 个顶点和 $M$ 条边的简单连通无向图 $G$。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。 第 $i$ 条边是连接顶点 $a_i$ 和 $b_i$ 的无向边。保证由顶点 $1,2,\ldots,N$ 和边 $1,2,\ldots,N-1$ 构成的子图是 $G$ 的一棵生成树。 如果对边赋予权值，使得由顶点 $1,2,\ldots,N$ 和边 $1,2,\ldots,N-1$ 构成的树成为 $G$ 的最小生成树，则称这样的权值分配为“良好分配”。 每条边都要被分配一个 $1$ 到 $M$ 的互不相同的整数权值。这样的分配方式共有 $M!$ 种。在所有良好分配中，计算最小生成树中包含的边的权值之和，并将这些和的总和对 $10^9+7$ 取模后输出。

输入以如下格式从标准输入读入： > $N$ $M$ > $a_1$ $b_1$ > $\vdots$ > $a_M$ $b_M$

输出答案。

## 限制条件 - 所有输入均为整数。 - $2 \leq N \leq 20$ - $N-1 \leq M \leq \frac{N(N-1)}{2}$ - $1 \leq a_i, b_i \leq N$ - 图 $G$ 中不存在自环或重边。 - 由顶点 $1,2,\ldots,N$ 和边 $1,2,\ldots,N-1$ 构成的子图是 $G$ 的一棵生成树。 ## 样例解释 1 - 只有当第 $3$ 条边被分配权值 $3$ 时，才是良好分配。 - 在这些良好分配中，最小生成树中包含的边的权值之和为 $3$，良好分配的数量为 $2$，因此答案为 $6$。 ## 样例解释 3 - 请将总和对 $10^9+7$ 取模后输出。 由 ChatGPT 4.1 翻译