P17477 [ICPC 2018 Jiaozuo R] 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.