Bessie has a collection of connected, undirected graphs G[1]
, G[2]
, ..., G[k]
. Gi
(1 ≤ i ≤ k) has exactly n[i]
(n[i]
≥ 2) vertices labeled 1..n[i]
and m[i]
(m[i]
≥ n[i]
− 1) edges. Each G[i]
may contain self-loops, but not multiple edges between the same pair of vertices.
Now Elsie creates a new undirected graph G with n[1]
* n[2]
* ... * n[k]
vertices, each labeled by a k-tuple (j[1]
, j[2]
,..., j[k]
) where 1 ≤ j[i]
≤ n[i]
. In G, two vertices (j[1]
, j[2]
,...,j[k]
) and (k[1]
, k[2]
,..., k[k]
) are connected by an edge if for all i (1 ≤ i ≤ k), j[i]
and k[i]
are connected by an edge in G[i]
.
Define the distance between two vertices in G that lie in the same connected component to be the minimum number of edges along a path from one vertex to the other. Compute the sum of the distances between vertex (1, 1,..., 1) and every vertex in the same component as it in G, modulo 10^9
+ 7.
The first line contains k (2 ≤ k ≤ 5 * 10^4
), the number of graphs.
Each graph description starts with n[i]
and m[i]
on a single line, followed by m[i]
edges.
Consecutive graphs are separated by newlines for readability. It is guaranteed that ∑ n[i]
≤ 10^5
and ∑ m[i]
≤ 2 * 10^5
.
Print the sum of the distances between vertex (1, 1,..., 1) and every vertex that is reachable from it, modulo 10^9
+ 7.
G contains 2 * 4 = 8 vertices, 4 of which are not connected to vertex (1, 1). There are 2 vertices that are distance 1 away from (1, 1) and 1 that is distance 2 away. So the answer is 2 * 1 + 1 * 2 = 4.
G contains 4 * 6 * 7 = 168 vertices, all of which are connected to vertex (1, 1, 1). The number of vertices that are distance i away from (1, 1, 1) for each i ∈ [1, 7] is given by the i-th element of the following array: [4, 23, 28, 36, 40, 24, 12].