[USACO21JAN] Sum of Distances P

题目描述

Bessie 有一些无向连通图 $G_1,G_2,…,G_K$($2≤K≤5⋅10^4$)。对于每一个 $1≤i≤K$,$G_i$ 有 $N_i$($N_i≥2$)个编号为 $1…N_i$ 的结点与 $M_i$($M_i≥N_i−1$)条边。$G_i$ 可能含有自环,但同一对结点之间不会存在多条边。 现在 Elsie 用 $N_1⋅N_2⋯N_K$ 个结点建立了一个新的无向图 $G$,每个结点用一个 $K$ 元组 $(j_1,j_2,…,j_K)$ 标号,其中 $1≤j_i≤N_i$。若对于所有的 $1≤i≤K$,$j_i$ 与 $k_i$ 在 $G_i$ 中连有一条边,则在 $G$ 中结点 $(j_1,j_2,…,j_K)$ 和 $(k_1,k_2,…,k_K)$ 之间连有一条边。 定义 $G$ 中位于同一连通分量的两个结点的 *距离* 为从一个结点到另一个结点的路径上的最小边数。计算 $G$ 中结点 $(1,1,…,1)$ 与所有与其在同一连通分量的结点的距离之和,对 $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$ 取模。

输入输出样例

输入样例 #1

2

2 1
1 2

4 4
1 2
2 3
3 4
4 1

输出样例 #1

4

输入样例 #2

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

输出样例 #2

706

说明

#### 样例 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,7]$,与结点 $(1,1,1)$ 距离为 $i$ 的结点数量为下列数组中的第 $i$ 个元素:$[4,23,28,36,40,24,12]$。 #### 测试点特性 - 测试点 $3-4$ 满足 $∏N_i≤300$。 - 测试点 $5-10$ 满足 $∑N_i≤300$。 - 测试点 $11-20$ 没有额外限制。 供题:Benjamin Qi