Problem Description

Bessie has some undirected connected graphs $G_1,G_2,\dots,G_K$ ($2 \le K \le 5 \cdot 10^4$). For each $1 \le i \le K$, $G_i$ has $N_i$ ($N_i \ge 2$) vertices numbered $1 \dots N_i$ and $M_i$ ($M_i \ge N_i - 1$) edges. $G_i$ may contain self-loops, but there are no multiple edges between the same pair of vertices.

Now Elsie builds a new undirected graph $G$ with $N_1 \cdot N_2 \cdots N_K$ vertices. Each vertex is labeled by a $K$-tuple $(j_1,j_2,\dots,j_K)$, where $1 \le j_i \le N_i$. If for all $1 \le i \le K$, $j_i$ and $k_i$ are connected by an edge in $G_i$, then there is an edge in $G$ between vertices $(j_1,j_2,\dots,j_K)$ and $(k_1,k_2,\dots,k_K)$.

Define the distance between two vertices in the same connected component of $G$ as the minimum number of edges on a path from one to the other. Compute the sum of distances from vertex $(1,1,\dots,1)$ to all vertices in the same connected component as it, modulo $10^9+7$.

Input Format

The first line contains $K$, the number of graphs.

The first line of each graph description contains $N_i$ and $M_i$, followed by $M_i$ edges.

For readability, there is a blank line between adjacent graphs. The input guarantees that $∑N_i \le 10^5$ and $∑M_i \le 2 \cdot 10^5$.

Output Format

Output the sum of distances from vertex $(1,1,\dots,1)$ to all vertices reachable from it, modulo $10^9+7$.

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

4

3

4 4
1 2
2 3
3 1
3 4

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

7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1

706

Hint

Sample 1 Explanation

$G$ contains $2 \cdot 4 = 8$ vertices, and $4$ of them are not connected to vertex $(1,1)$. There are $2$ vertices at distance $1$ from $(1,1)$, and $1$ vertex at distance $2$. So the answer is $2 \cdot 1 + 1 \cdot 2 = 4$.

Sample 2 Explanation

$G$ contains $4 \cdot 6 \cdot 7 = 168$ vertices, all connected to vertex $(1,1,1)$. For each $i \in [1,7]$, the number of vertices at distance $i$ from $(1,1,1)$ is the $i$-th element of the following array: $[4,23,28,36,40,24,12]$.

Testdata Properties

• Testdata $3-4$ satisfies $∏N_i \le 300$.
• Testdata $5-10$ satisfies $∑N_i \le 300$.
• Testdata $11-20$ has no additional restrictions.

Problem by: Benjamin Qi.

Translated by ChatGPT 5