You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

边号排序

题目描述

Cuber QQ 会给你一张 $n$ 个点 $m$ 条边的连通简单无向图 $G$，点从 $1$ 到 $n$ 编号，边从 $1$ 到 $m$ 编号。

Cuber QQ 给定的编号是精心设计的，编号为 $1$ 到 $n-1$ 的边恰好会构成图 $G$ 的一棵生成树 $T$。

Cuber QQ 要求你分别将 $[1,m]$ 中 $m$ 个数分配给每条边作为边权，需要保证任意两条边的边权都是不同的，即所有边的边权构成一个 $m$ 的全排列。

如果某一个分配方案中 $T$ 恰好是图 $G$ 的最小生成树，Cuber QQ 就认为这是一个优美的分配方案，而此时 $T$ 的边权和为该方案的价值。

现在 Cuber QQ 想知道所有优美的分配方案的价值总和。

输入格式

第一行两个整数 $N,M$ ，接下来 $M$ 行每行两个整数 $a_i,b_i$ 表示一条边。

输出格式

一个整数表示答案。

样例 #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\ \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$ 的生成树。

样例解释 1

一个方案是优美的当且仅当 $3$ 号边的边权是 $3$ ，在这些方案中最小生成树的边权和都是 $3$ ，共有 $2$ 种不同的分配方案，故总和是 $6$ 。