405671: GYM102028 L Connected Subgraphs

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