У Беси есть коллекция связных неориентированных графов G[1]
, G[2]
, ..., G[k]
(2 ≤ k ≤ 5 * 10^4
). Для каждого i (1 ≤ i ≤ k), G[i]
имеет ровно n[i]
(n[i]
≥ 2) вершин, помеченных 1..n[i]
и m[i]
(m[i]
≥ n[i]
− 1) ребер. Каждый G[i]
может содержать циклы, но нет двух и более ребер между парой вершин.
Сейчас Эльза создаёт новый неориентированный граф G с n[1]
* n[2]
* ... * n[k]
вершинами, каждая из которых помечена k-плетом (j[1]
, j[2]
,..., j[k]
), где 1 ≤ j[i]
≤ n[i]
. В G две вершины (j[1]
, j[2]
,...,j[k]
) и (k[1]
, k[2]
,..., k[k]
) соединены ребром, если для всех i (1 ≤ i ≤ k), j[i]
и k[i]
соединены ребром в G[i]
.
Определим расстояние между двумя вершинами в G которые лежат в одной и той же связной компоненте как минимальное количество ребер на пути из одной вершины в другую. Вычислите сумму расстояний между вершиной (1, 1, ..., 1) и каждой вершиной в этой же компоненте в G по модулю 10^9
+ 7.
Первая строка содердит k, количество графов.
Описание каждого графа начинается с n[i]
и m[i]
в одной строке, за которой следуют m[i]
ребер.
Последовательные графы разделены пустыми строками для читабельности. Гарантируется, что ∑ n[i]
≤ 10^5
и ∑ m[i]
≤ 2 * 10^5
.
Сумма расстояний от вершины (1, 1, ..., 1) и каждой вершины достижимой от неё по модулю 10^9
+ 7.
G содержит 2 * 4 = 8 вершин, 4 из которых не соединены с вершиной (1, 1). Имеется 2 вершины на расстоянии 1 от вершины (1, 1) и 1 вершина на расстоянии 2. Поэтому ответ 2 * 1 + 1 * 2 = 4.
G содержит 4 * 6 * 7 = 168 вершин, каждая из которых соединена с вершиной (1, 1, 1). Количество вершин на расстоянии i от вершины (1, 1, 1) для каждого i ∈ [1, 7] задано i-ым элементом следующего массива: [4, 23, 28, 36, 40, 24, 12].