Сумма расстояний
Сумма расстояний
У Беси есть коллекция связных неориентированных графов G1
, G2
, ..., Gk
(2 ≤ k ≤ 5 * 104
). Для каждого i (1 ≤ i ≤ k), Gi
имеет ровно ni
(ni
≥ 2) вершин, помеченных 1..ni
и mi
(mi
≥ ni
− 1) ребер. Каждый Gi
может содержать циклы, но нет двух и более ребер между парой вершин.
Сейчас Эльза создаёт новый неориентированный граф G с n1
* n2
* ... * nk
вершинами, каждая из которых помечена k-плетом (j1
, j2
,..., jk
), где 1 ≤ ji
≤ ni
. В G две вершины (j1
, j2
,...,jk
) и (k1
, k2
,..., kk
) соединены ребром, если для всех i (1 ≤ i ≤ k), ji
и ki
соединены ребром в Gi
.
Определим расстояние между двумя вершинами в G которые лежат в одной и той же связной компоненте как минимальное количество ребер на пути из одной вершины в другую. Вычислите сумму расстояний между вершиной (1, 1, ..., 1) и каждой вершиной в этой же компоненте в G по модулю 109
+ 7.
Входные данные
Первая строка содердит k, количество графов.
Описание каждого графа начинается с ni
и mi
в одной строке, за которой следуют mi
ребер.
Последовательные графы разделены пустыми строками для читабельности. Гарантируется, что ∑ ni
≤ 105
и ∑ mi
≤ 2 * 105
.
Выходные данные
Сумма расстояний от вершины (1, 1, ..., 1) и каждой вершины достижимой от неё по модулю 109
+ 7.
Пример 1
G содержит 2 * 4 = 8 вершин, 4 из которых не соединены с вершиной (1, 1). Имеется 2 вершины на расстоянии 1 от вершины (1, 1) и 1 вершина на расстоянии 2. Поэтому ответ 2 * 1 + 1 * 2 = 4.
Пример 2
G содержит 4 * 6 * 7 = 168 вершин, каждая из которых соединена с вершиной (1, 1, 1). Количество вершин на расстоянии i от вершины (1, 1, 1) для каждого i ∈ [1, 7] задано i-ым элементом следующего массива: [4, 23, 28, 36, 40, 24, 12].
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