405612: GYM102012 B Rikka with Line Graphs

Several years of ACM-ICPC experience enables Rikka, as a student at Keping University, to catch the tide of the algorithm development.

Over the courses for this semester, Rikka made a deep study of line graphs. In the mathematical discipline of graph theory, the line graph of a simple undirected graph $$$G$$$ is another simple undirected graph $$$L(G)$$$ that represents the adjacency between every two edges in $$$G$$$. Precisely speaking, for an undirected graph $$$G$$$ without loops or multiple edges, its line graph $$$L(G)$$$ is a graph such that

• each vertex of $$$L(G)$$$ represents an edge of $$$G$$$; and
• two vertices of $$$L(G)$$$ are adjacent if and only if their corresponding edges share a common endpoint in $$$G$$$.

Given a simple undirected graph $$$G$$$, Rikka's study aims to count the number of vertices in its line graph. Now she decides to show you some critical results of her early study, concerning the number of vertices in the line graph of $$$G$$$, $$$L(G)$$$, the line graph of the line graph of $$$G$$$, $$$L^2(G)$$$ (i. e. $$$L(L(G))$$$), and so forth, denoted by $$$|V(L(G))|$$$, $$$|V(L^2(G))|$$$, $$$\cdots$$$.

By the definition of an undirected graph with $$$n$$$ vertices and $$$m$$$ edges, we know that

$$$$$$|V(L(G))| = \sum_e 1 = m = \frac{1}{2} \sum_u d_1(u),$$$$$$

where $$$d_1(u)$$$ represents the degree of vertex $$$u$$$ in $$$G$$$.

Once we know how to count, for any edge $$$e$$$ in $$$G$$$, the number of edges which share a common endpoint with $$$e$$$, or equally speaking the degree of $$$e$$$ in $$$L(G)$$$, which is denoted by $$$d'_1(e)$$$, we have

$$$$$$|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).$$$$$$

A similar easy analysis can help us to calculate $$$|V(L^3(G))|$$$, and an excellent result in Rikka's known work, which was published in the 2018 JheZiang Olympiad in Informatics, reveals the number of vertices in $$$L^4(G)$$$ as

$$$$$$\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}$$$$$$

where $$$d_2(u)$$$ is the summation of degrees of all adjacent vertices of $$$u$$$ in $$$G$$$, and when considering the degrees squared of all adjacent vertices of $$$u$$$, $$$d_{2, 2}(u)$$$ is the summation of them all.

Based on the equation $$$L^5(G) = L^4(L(G))$$$, her newest work made a further development. She extrapolates from the result about $$$L^4(G)$$$ a linear computable method to calculate the number of vertices in $$$L^5(G)$$$ in time complexity $$$O(n + m)$$$. Rikka pointed out that the data about vertices required in the summation form of $$$|V(L^4(G))|$$$ imply new data about edges with similar definitions. Actually, the relationship between $$$d_1$$$ and $$$d'_1$$$ is the easiest correspondence. A harder one is described as the one between $$$d_2$$$ and $$$d'_2$$$. Luckily, we can calculate all these new data which we need about the edges in linear time. Thus an attempt replacing the summation of vertices by a summation of edges provides a strict formula for the number of vertices in $$$L^5(G)$$$.

Now you must try to go with the current of the times. In this problem, for an undirected simple graph $$$G$$$, you are asked to calculate the number of vertices in $$$L^6(G)$$$ and output the number modulo $$$(10^9 + 7)$$$.

The input contains several test cases, and the first line contains a single integer $$$T$$$ ($$$1 \le T \le 10$$$), the number of test cases.

For each test case, the first line contains two integers $$$n$$$ ($$$1 \le n \le 10^5$$$) and $$$m$$$ ($$$0 \le m \le 2 \times 10^5$$$), the number of vertices and edges in the given simple undirected graph $$$G$$$.

Then $$$m$$$ lines follow, describing all edges of the graph. Each line of them contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), representing an edge between the $$$u$$$-th vertex and the $$$v$$$-th vertex.

The input guarantees that the given graph for each test case contains no loops or multiple edges.

For each test case, output a single line with a single integer, the remainder of the number of vertices in $$$L^6(G)$$$ divided by $$$(10^9 + 7)$$$.

2
4 4
1 2
2 3
3 1
4 1
4 4
1 2
2 3
3 4
4 1

396
4