Сума відстаней#11204

Сума відстаней

1 секунда

128 мегабайтів

Складна

У Бесі є колекція зв'язних неорієнтованих графів $G_{1}$ G_1, $G_{2}$ G_2, ..., $G_{k}$ G_k (2 ≤ k ≤ 5 * $1 0^{4}$ 10^4). Для кожного i (1 ≤ i ≤ k), $G_{i}$ G_i має рівно $n_{i}$ n_i ( $n_{i}$ n_i ≥ 2) вершин, позначених 1.. $n_{i}$ n_i, і $m_{i}$ m_i ( $m_{i}$ m_i ≥ $n_{i}$ n_i − 1) ребер. Кожен $G_{i}$ G_i може містити цикли, але не має двох і більше ребер між парою вершин.

Ельза створює новий неорієнтований граф G з $n_{1}$ n_1 * $n_{2}$ n_2 * ... * $n_{k}$ n_k вершинами, кожна з яких позначена k-плетом ( $j_{1}$ j_1, $j_{2}$ j_2, ..., $j_{k}$ j_k), де 1 ≤ $j_{i}$ j_i ≤ $n_{i}$ n_i. У G дві вершини ( $j_{1}$ j_1, $j_{2}$ j_2, ..., $j_{k}$ j_k) і ( $k_{1}$ k_1, $k_{2}$ k_2, ..., $k_{k}$ k_k) з'єднані ребром, якщо для всіх i (1 ≤ i ≤ k), $j_{i}$ j_i і $k_{i}$ k_i з'єднані ребром в $G_{i}$ G_i.

Відстань між двома вершинами в G, які лежать в одній і тій же зв'язній компоненті, визначається як мінімальна кількість ребер на шляху з однієї вершини в іншу. Обчисліть суму відстаней між вершиною (1, 1, ..., 1) і кожною вершиною в цій же компоненті в G за модулем $1 0^{9}$ 10^9 + 7.

Вхідні дані

Перший рядок містить k, кількість графів.

Опис кожного графа починається з $n_{i}$ n_i і $m_{i}$ m_i в одному рядку, за яким слідують $m_{i}$ m_i ребер.

Послідовні графи розділені порожніми рядками для читабельності. Гарантовано, що ∑ $n_{i}$ n_i ≤ $1 0^{5}$ 10^5 і ∑ $m_{i}$ m_i ≤ 2 * $1 0^{5}$ 10^5.

Вихідні дані

Сума відстаней від вершини (1, 1, ..., 1) до кожної вершини, досяжної від неї, за модулем $1 0^{9}$ 10^9 + 7.

Приклади

Приклад 1

Приклад 2

Примітка

Приклад 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].