Distance Sum in the Tensor Product Graph

Bessie is given K undirected connected graphs \(G_1,G_2,\dots,G_K\) (where \(2\le K\le5\cdot10^4\)). For each \(1\le i\le K\), graph \(G_i\) has \(N_i\) (with \(N_i\ge 2\)) vertices labeled \(1,2,\dots,N_i\) and \(M_i\) edges (with \(M_i\ge N_i-1\)). Note that \(G_i\) may contain self-loops but there is at most one edge between any two distinct vertices.

Elsie now constructs a new undirected graph \(G\) using \(N_1\cdot N_2\cdots N_K\) nodes. Each node is labeled with a \(K\)-tuple \((j_1,j_2,\dots,j_K)\) where \(1\le j_i\le N_i\). Two nodes \((j_1,j_2,\dots,j_K)\) and \((k_1,k_2,\dots,k_K)\) are connected by an edge in \(G\) if and only if for every \(1\le i\le K\), vertices \(j_i\) and \(k_i\) are adjacent in \(G_i\) (i.e. there is an edge between them in \(G_i\)). Such a product graph is often called the tensor product of the graphs.

For any two vertices in the same connected component of \(G\), define their distance as the minimum number of edges in a path connecting them. Your task is to compute, modulo \(10^9+7\), the sum of distances from the vertex \((1,1,\dots,1)\) to every vertex in the same connected component as \((1,1,\dots,1)\) in \(G\).

Note: In a valid walk in \(G\) of length \(L\), each coordinate must follow a walk in the corresponding \(G_i\) of exactly \(L\) steps. Hence, a vertex \( (j_1,j_2,\dots,j_K) \) is reachable from \((1,1,\dots,1)\) if and only if for every \(i\), there exists a walk in \(G_i\) from vertex 1 to vertex \(j_i\) of length \(L\) (taking self-loops into account when necessary). Due to the potentially enormous size of \(G\), a direct construction of \(G\) is infeasible. However, the constraints in this problem allow efficient solutions based on a multi‐dimensional BFS (which works for small instances) or other combinatorial techniques for larger instances. In the sample test cases below the sizes are small.

inputFormat

The input begins with a line containing a single integer \(K\) — the number of graphs. Then for each graph \(G_i\) (for \(i=1,2,\dots,K\)) the input is given as follows:

• A line containing two integers \(N_i\) and \(M_i\) — the number of vertices and edges in \(G_i\).
• Then \(M_i\) lines follow, each containing two integers \(u\) and \(v\) (\(1\le u,v\le N_i\)) indicating an undirected edge between vertices \(u\) and \(v\). Note that \(G_i\) may contain self-loops but there is at most one edge between any two distinct vertices.

outputFormat

Output a single integer, the sum of the distances from vertex \((1,1,\dots,1)\) to every vertex in its connected component in \(G\), modulo \(10^9+7\).

sample

2
2 1
1 2
2 1
1 2

1