J. Bald and Eslam
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bald is taking Calculus this semester. His professor, Dr. Eslam, often talks about graphs of functions. When Bald later encountered a problem in Graph Theory, he mistakenly thought it was the same kind of "graph". Confused, he went back to Dr. Eslam for help.

You are given an undirected connected graph$$$^\dagger$$$ $$$G$$$ consisting of $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered from $$$1$$$ to $$$n$$$.

Let $$$f_G(v)$$$ denote the maximum number of distinct vertices that can be visited starting from vertex $$$v$$$ in a graph $$$G$$$.

Consider the following random experiment to sample a pair $$$(G', v)$$$ from $$$G$$$ (where $$$G'$$$ is a graph and $$$v$$$ is a vertex in $$$G'$$$):

  1. Sample a vertex $$$v$$$ uniformly at random from $$$\{1,2,\dots,n\}$$$.
  2. If $$$\deg(v) \ge 1$$$, sample an edge $$$e$$$ incident on $$$v$$$ uniformly at random.
  3. Let $$$G'$$$ be the graph obtained by deleting $$$e$$$ from $$$G$$$ (if $$$\deg(v)=0$$$, then $$$G'=G$$$).
  4. Return the pair $$$(G',v)$$$.

Your task is to compute the expected value of $$$f_{G'}(v)$$$ over all sampled $$$(G', v)$$$ by the above experiment.

Since the answer can be a rational number, output it modulo $$$10^9+7$$$. Formally, if the expected value is $$$\tfrac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are integers and $$$q \not\equiv 0 \pmod{10^9+7}$$$, then you should output $$$p \cdot q^{-1} \bmod (10^9+7)$$$ where $$$q^{-1}$$$ denotes the modular inverse of $$$q$$$ modulo $$$10^9+7$$$.

Dr. Eslam does not like this kind of graphs; he likes the other type. So you are now in charge of solving this problem for Bald.

$$$\rule{20em}{0.4pt}$$$

$$$^\dagger$$$ A connected undirected graph is a graph containing vertices and edges where each edge can be traversed in either direction, and there is a path (a sequence of edges) between any two vertices in the graph.

Input

The input consists of multiple test cases.

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 10^5$$$) — the number of test cases.

Each test case begins with a line containing two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$n - 1 \leq m \leq \min(2 \cdot 10^5, \tfrac{n(n-1)}{2}$$$)) — the number of vertices and edges in the graph.

Then $$$m$$$ lines follow, each containing two integers $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \ne v_i$$$) — describing an undirected edge between vertices $$$u_i$$$ and $$$v_i$$$.

It is guaranteed that:

  • the graph is connected,
  • there are no self-loops or multiple edges,
  • the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$,
  • the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Example
Input
3
3 2
1 2
2 3
7 7
1 2
1 3
1 5
1 6
3 4
3 6
5 7
4 4
1 2
2 3
2 4
3 4
Output
333333337
845238105
166666671
Note

Consider the first test case, where the graph is a path with $$$n=3$$$ and edges $$$1-2,2-3$$$. Let us consider each vertex separately:

  • Start at vertex $$$1$$$: it has degree $$$1$$$. Deleting its only edge leaves it alone, so you can not visit any other vertices. Hence, its contribution is $$$1.$$$
  • Start at vertex $$$2$$$: it has degree $$$2$$$. Deleting edge $$$2-1$$$ would enable you to visit vertices $$$2$$$ and $$$3$$$; deleting $$$2-3$$$ leaves would enable you to visit vertices $$$2$$$ and $$$1$$$. Summed over its incident edges this gives a contribution of $$$\frac{2 + 2}{2} = 2.$$$
  • Start at vertex $$$3$$$: symmetric to vertex $$$1$$$, contribution $$$1$$$.

Averaging over the three starting vertices gives $$$\frac{1+2+1}{3} = \frac{4}{3}$$$.

Converting to modulo $$$10^9+7$$$: $$$3^{-1}=333333336$$$, hence $$$\frac{4}{3} \bmod 10^9+7 = 4 \cdot 333333336 \bmod 10^9+7 = 333333337$$$.