A6404. 「USACO 2021.1 Platinum」Sum of Distances

**题目来自 [USACO 2021 January Contest, Platinum](http://usaco.org/index.php?page=jan21results) Problem 1. [Sum of Distances](http://usaco.org/index.php?page=viewproblem2&cpid=1092&lang=zh)。**

Bessie 有一些无向连通图 $G_1, G_2, \ldots , G_K$（$2 \le K \le 5 \times {10}^4$）。对于每一个 $1 \le i \le K$，$G_i$ 有 $N_i$（$N_i \ge 2$）个编号为 $1 \ldots N_i$ 的结点与 $M_i$（$M_i \ge N_i - 1$）条边。$G_i$ 可能含有自环，但同一对结点之间不会存在多条边。

现在 Elsie 用 $N_1 \cdot N_2 \cdot \ldots \cdot N_K$ 个结点建立了一个新的无向图 $G$，每个结点用一个 $K$ 元组 $(j_1, j_2, \ldots , j_K)$ 标号，其中 $1 \le j_i \le N_i$。若对于所有的 $1 \le i \le K$，$j_i$ 与 $k_i$ 在 $G_i$ 中连有一条边，则在 $G$ 中结点 $(j_1, j_2, \ldots , j_K)$ 和 $(k_1, k_2, \ldots , k_K)$ 之间连有一条边。

定义 $G$ 中位于同一连通分量的两个结点的**距离**为从一个结点到另一个结点的路径上的最小边数。计算 $G$ 中结点 $(1, 1, \ldots, 1)$ 与所有与其在同一连通分量的结点的距离之和，对 ${10}^9 + 7$ 取模。

输入的第一行包含 $K$，为图的数量。

每个图的描述的第一行包含 $N_i$ 和 $M_i$，以下是 $M_i$ 条边。

为提高可读性，相邻的图之间用一个空行隔开。输入保证 $\sum N_i \le {10}^5$ 以及 $\sum M_i \le 2 \times {10}^5$。

输出结点 $(1, 1, \ldots, 1)$ 与所有该结点可以到达的结点的距离之和，对 ${10}^9 + 7$ 取模。

测试点 $3 \sim 4$ 满足 $\prod N_i \le 300$。
测试点 $5 \sim 10$ 满足 $\sum N_i \le 300$。
测试点 $11 \sim 20$ 没有额外限制。