题目描述

An algorithm master in graph theory would never endure any disconnected subgraph.

An esthetician would only consider edge-induced subgraphs as necessary subgraphs.

An OCD patient would always choose a subgraph from a given simple undirected graph randomly.

Those are why Picard asks you to calculate, for choosing four different edges from a given simple undirected graph with equal probability among all possible ways, the probability that the edge-induced subgraph formed by chosen edges is connected. Here we say a subset of edges in the graph together with all vertices that are endpoints of edges in the subset form an edge-induced subgraph.

To avoid any precision issue, Picard denotes the probability as $p$ and the number of edges as $m$, and you should report the value $\left(p \cdot \binom{m}{4}\right) \bmod (10^9 + 7)$. It is easy to show that $p \cdot \binom{m}{4}$ is an integer.

输入格式

The input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $10$.

For each test case, the first line contains two integers $n$ and $m$ indicating the numbers of vertices and edges in the given simple undirected graph respectively, where $4 \leq n \leq 10^5$ and $4 \leq m \leq 2 \times 10^5$.

The following $m$ lines describe all edges of the graph, the $i$-th line of which contains two integers $u$ and $v$ which represent an edge between the $u$-th vertex and the $v$-th vertex, where $1 \leq u, v \leq n$ and $u \neq v$.

We guarantee that the given graph contains no loops or multiple edges.

输出格式

For each test case, output a line containing an integer corresponding to the value $\left(p \cdot \binom{m}{4}\right) \bmod (10^9 + 7)$, where $p$ indicates the probability which you are asked to calculate.

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