分数: 1200 点
问题陈述
给你一个简单的连通无向图 G 组成 N 顶点和 M 边缘。 顶点已编号 1 to N,并且边缘已编号 1 to M.
边缘 i 连接顶点 a_i 和 b_i 双向。 保证由Vertex组成的子图 1,2,\ldots,N 和边缘 1,2,\ldots,N-1 是一棵生成树 G.
边缘的权重分配称为 配置好 当树由顶点组成时 1,2,\ldots,N 和边缘 1,2,\ldots,N-1 是最小生成树 G.
有 M! 在之间分配不同整数权重的边的方法 1 和 M。 对于其中每个好的分配,找到最小生成树中边的总权重,并打印这些总权重的模数之和 10^{9}+7.
约束
- 输入中的所有值都是整数。
- 2 \leq N \leq 20
- N-1 \leq M \leq N(N-1)/2
- 1 \leq a_i, b_i \leq N
- G 没有自环或多重边。
- 由 Vertex 组成的子图 1,2,\ldots,N 和边缘 1,2,\ldots,N-1 是一棵生成树 G.
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 \vdots a_M b_M
输出
打印答案。
示例输入 1
3 3 1 2 2 3 1 3
示例输出 1
6
仅当 Edge 时分配才是好的 3 有重量 3。对于这些良好的分配,最小生成树中边的总权重为 3,并且有两个好的分配,所以答案是 6.
示例输入 2
4 4 1 2 3 2 3 4 1 3
示例输出 2
50
示例输入 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
打印这些总重量的模数之和 10^{9}+7.