F - Edge Ordering 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 1200 点

問題文

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 で割ったあまりを出力してください。

制約

  • 入力は全て整数
  • 2 \leq N \leq 20
  • N-1 \leq M \leq N(N-1)/2
  • 1 \leq a_i, b_i \leq N
  • G に自己ループや多重辺は存在しない
  • 頂点 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
  • 辺 3 に重み 3 が割り当てられたときに限り、良い割り当てとなります。
  • これらの良い割り当てにおける G の最小全域木に含まれる辺の重みの和は 3 であり、良い割り当ての個数は 2 つなので答えは 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 で割ったあまりを出力してください。

Score : 1200 points

Problem Statement

You are given a simple connected undirected graph G consisting of N vertices and M edges. The vertices are numbered 1 to N, and the edges are numbered 1 to M.

Edge i connects Vertex a_i and b_i bidirectionally. It is guaranteed that the subgraph consisting of Vertex 1,2,\ldots,N and Edge 1,2,\ldots,N-1 is a spanning tree of G.

An allocation of weights to the edges is called a good allocation when the tree consisting of Vertex 1,2,\ldots,N and Edge 1,2,\ldots,N-1 is a minimum spanning tree of G.

There are M! ways to allocate the edges distinct integer weights between 1 and M. For each good allocation among those, find the total weight of the edges in the minimum spanning tree, and print the sum of those total weights modulo 10^{9}+7.

Constraints

  • All values in input are integers.
  • 2 \leq N \leq 20
  • N-1 \leq M \leq N(N-1)/2
  • 1 \leq a_i, b_i \leq N
  • G does not have self-loops or multiple edges.
  • The subgraph consisting of Vertex 1,2,\ldots,N and Edge 1,2,\ldots,N-1 is a spanning tree of G.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
\vdots
a_M b_M

Output

Print the answer.

Sample Input 1

3 3
1 2
2 3
1 3

Sample Output 1

6

An allocation is good only if Edge 3 has the weight 3. For these good allocations, the total weight of the edges in the minimum spanning tree is 3, and there are two good allocations, so the answer is 6.

Sample Input 2

4 4
1 2
3 2
3 4
1 3

Sample Output 2

50

Sample Input 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

Sample Output 3

657573092

Print the sum of those total weights modulo 10^{9}+7.