题目描述

一位图论算法大师永远无法容忍任何不连通的子图。

一位唯美主义者只会将边诱导子图视为有价值的子图。

一位强迫症患者总是会从一张给定的简单无向图中随机选取一个子图。

正因如此，Picard 希望你计算：从一张给定的简单无向图中等可能地选取四条不同的边，由这四条边构成的边诱导子图是连通的概率。定义如下：图中一个边子集，连同该子集中所有边的端点构成的顶点集，一起形成边诱导子图。

为避免任何精度问题，Picard 将该概率记作 $p$，并将边数记作 $m$，你需要输出 $\left(p \cdot \binom{m}{4}\right) \bmod (10^9 + 7)$ 的值。容易证明 $p \cdot \binom{m}{4}$ 是一个整数。

输入格式

输入包含多组测试数据，第一行包含一个正整数 $T$，表示测试数据组数，最多为 $10$。

对于每组测试数据，第一行包含两个整数 $n$ 和 $m$，分别表示给定简单无向图的顶点数和边数，满足 $4 \leq n \leq 10^5$，$4 \leq m \leq 2 \times 10^5$。

接下来的 $m$ 行描述图中的所有边，第 $i$ 行包含两个整数 $u$ 和 $v$，表示第 $u$ 个顶点与第 $v$ 个顶点之间的一条边，满足 $1 \leq u, v \leq n$ 且 $u \neq v$。

我们保证给定的图不包含自环或多重边。

输出格式

对于每组测试数据，输出一行一个整数，对应 $\left(p \cdot \binom{m}{4}\right) \bmod (10^9 + 7)$ 的值，其中 $p$ 表示你需要计算的那个概率。

2
4 4
1 2
2 3
3 4
4 1
4 6
1 2
1 3
1 4
2 3
2 4
3 4

1
15

提示

翻译由 DeepSeek V4 Pro 完成