Page not loading? Try clicking here.
Placeholder

#5785

Sum of Distances 1s 512MB

Problems

Bessie has a collection of connected, undirected graphs G_1,G_2,…,G_K (2≤K≤5⋅10^4). For each 1≤i≤K, G_i 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 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

.


Input

The first line contains K, 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.


Output

The sum of the distances between vertex (1,1,…,1) and every vertex that is reachable from it, modulo 10^9+7.


Example #1

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1
4

G contains 2⋅4=8vertices, 4 of which are not connected to vertex (1,1). There are 2 vertices that are distance 1away from (1,1) and 1 that is distance 2 away. So the answer is 2⋅1+1⋅2=4.


Example #2

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

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]

.


Source

USACO 2021 January Platinum

You must sign in to write code.