QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100
[0]

# 2028. Sum of Distances

Statistics

Bessie has a collection of connected, undirected graphs G1,G2,,GK (2K5104). For each 1iK, Gi has exactly Ni (Ni2) vertices labeled 1Ni and Mi (MiNi1) edges. Each Gi may contain self-loops, but not multiple edges between the same pair of vertices.

Now Elsie creates a new undirected graph G with N1N2NK vertices, each labeled by a K-tuple (j1,j2,,jK) where 1jiNi. In G, two vertices (j1,j2,,jK) and (k1,k2,,kK) are connected by an edge if for all 1iK, ji and ki are connected by an edge in Gi.

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 109+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains K, the number of graphs.

Each graph description starts with Ni and Mi on a single line, followed by Mi edges.

Consecutive graphs are separated by newlines for readability. It is guaranteed that Ni105 and Mi2105.

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

SAMPLE OUTPUT:

4
G contains 24=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 21+12=4.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

706
G contains 467=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].

SCORING:

  • Test cases 3-4 satisfy Ni300.
  • Test cases 5-10 satisfy Ni300.
  • Test cases 11-20 satisfy no additional constraints.

Problem credits: Benjamin Qi