← 返回题目列表

AtCoder · diverta2019_f

F. 边缘排序

中文机器翻译题面 查看原题

分数: 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.