P17419 [ICPC 2018 Xuzhou R] Rikka with Line Graphs

多年的 ACM-ICPC 经历使得珂普大学的学生 Rikka 能够紧跟算法发展的潮流。 在本学期的课程中，Rikka 对线图进行了深入的研究。在图论这一数学分支中，一个简单无向图 $G$ 的线图是另一个简单无向图 $L(G)$，它刻画了 $G$ 中每两条边之间的邻接关系。确切地说，对于一个不含自环或多重边的无向图 $G$，它的线图 $L(G)$ 是满足以下条件的图： * $L(G)$ 的每个顶点代表 $G$ 的一条边； * $L(G)$ 的两个顶点相邻，当且仅当它们所对应的边在 $G$ 中共用一个端点。 :::align{center}  ::: 给定一个简单无向图 $G$，Rikka 的研究旨在计算其线图的顶点数。现在她决定向你展示她早期研究的一些关键成果，这些成果涉及 $G$ 的线图 $L(G)$、$G$ 的线图的线图 $L^2(G)$（即 $L(L(G))$）等图直至任意次迭代线图的顶点数，记作 $|V(L(G))|$、$|V(L^2(G))|$、$\cdots$。 根据具有 $n$ 个顶点和 $m$ 条边的无向图的定义，我们知道 $$|V(L(G))| = \sum_e 1 = m = \frac{1}{2} \sum_u d_1(u),$$ 其中 $d_1(u)$ 表示 $G$ 中顶点 $u$ 的度数。 一旦我们懂得如何计算 $G$ 中任意一条边 $e$ 所关联的、与其共享端点的边的数目，换句话说，边 $e$ 在 $L(G)$ 中的度数，记作 $d_1^{'}(e)$，我们就可以得到 $$|V(L^2(G))| = \frac{1}{2} \sum_e d_1^{'}(e) = \frac{1}{2} \sum_{e = (u, v)} (d_1(u) - 1 + d_1(v) - 1) = \frac{1}{2} \sum_{u} d_1(u) (d_1(u) - 1).$$ 类似的简单分析可以帮助我们计算 $|V(L^3(G))|$，而 Rikka 已知工作中一个发表在 2018 年 JheZiang Olympiad in Informatics 上的杰出结果，则揭示了 $L^4(G)$ 的顶点数公式为 $$\begin{aligned}|V(L^4(G))| = \frac{1}{2} \sum_{u} &(2 d_1^2(u) - 13 d_1(u) + 21 + 4 d_2(u)) d_1(u) (d_1(u) - 1) \\ &-13 (d_1(u) - 1) d_2(u) + (d_1(u) - 2) d_{2, 2}(u) + d_2^2(u),\end{aligned}$$ 其中 $d_2(u)$ 表示 $G$ 中顶点 $u$ 的所有邻接顶点的度数之和，而 $d_{2, 2}(u)$ 则是 $u$ 的所有邻接顶点度数的平方之和。 基于等式 $L^5(G) = L^4(L(G))$，她最新的工作又向前推进了一步。她从 $L^4(G)$ 的结果出发，外推出了一种在 $O(n + m)$ 时间复杂度内计算 $L^5(G)$ 顶点数的线性时间方法。Rikka 指出，$|V(L^4(G))|$ 求和形式中所需的与顶点相关的数据，暗示着可以定义出与边相关的类似新数据。实际上，$d_1$ 与 $d_1^{'}$ 间的对应是最简单的一种。更复杂的一种被描述为 $d_2$ 与 $d_2^{'}$ 之间的关系。幸运的是，所有我们需要的这些与边有关的新数据都可以在线性时间内计算出来。因此，将关于顶点的求和替换为关于边的求和，就为 $L^5(G)$ 的顶点数提供了一个严格的公式。 现在你必须尝试跟上时代的步伐。本题中，对于一个简单无向图 $G$，请你计算 $L^6(G)$ 的顶点数，并输出该数对 $(10^9 + 7)$ 取模的结果。

输入包含多组测试数据，第一行包含一个整数 $T$（$1 \le T \le 10$），表示测试数据的组数。 对于每组测试数据，第一行包含两个整数 $n$（$1 \le n \le 10^5$）和 $m$（$0 \le m \le 2 \times 10^5$），分别表示给定简单无向图 $G$ 的顶点数和边数。 接下来 $m$ 行，每行描述图中的一条边。每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示第 $u$ 个顶点与第 $v$ 个顶点之间的一条边。 输入保证每组测试数据给出的图均不包含自环或多重边。

对于每组测试数据，输出一行一个整数，表示 $L^6(G)$ 的顶点数除以 $(10^9 + 7)$ 所得的余数。

翻译由 DeepSeek V4 Pro 完成