P7418 [USACO21FEB] Counting Graphs P

Bessie has a connected undirected graph $G$. $G$ has $N$ vertices numbered $1 \ldots N$ and $M$ edges ($1 \le N \le 10^2$, $N-1 \le M \le \frac{N^2+N}{2}$). $G$ may contain self-loops (an edge from a vertex to itself), but it does not contain multiple edges (multiple edges connecting the same pair of vertices). Let $f_G(a,b)$ be a boolean function. For each $1 \le a \le N$ and $0 \le b$, the function is true if there exists a path from vertex $1$ to vertex $a$ that uses exactly $b$ edges, and false otherwise. If an edge is traversed multiple times, it is counted that many times. Elsie wants to copy Bessie. Specifically, she wants to construct an undirected graph $G'$ such that for all $a$ and $b$, we have $f_{G'}(a,b)=f_G(a,b)$. Your task is to compute the number of graphs $G'$ that Elsie can construct, modulo $10^9+7$. Just like $G$, $G'$ may contain self-loops but cannot contain multiple edges (this means that for $N$ labeled vertices there are $2^{\frac{N^2+N}{2}}$ different graphs in total). Each input contains $T$ ($1 \le T \le \frac{10^5}{4}$) independent test cases. It is guaranteed that the sum of $N^2$ over all test cases does not exceed $10^5$.

The first line of input contains $T$, the number of test cases. The first line of each test case contains integers $N$ and $M$. Each of the next $M$ lines of the test case contains two integers $x$ and $y$ ($1 \le x \le y \le N$), meaning that there is an edge connecting $x$ and $y$ in $G$. For readability, adjacent test cases are separated by a blank line.

For each test case, output one line: the number of different graphs $G'$, modulo $10^9+7$.

#### Explanation for Sample 1: In the first test case, $G'$ can be equal to $G$, or one of the following two graphs: ``` 5 4 1 2 1 4 3 4 3 5 ``` ``` 5 5 1 2 2 3 1 4 3 4 3 5 ``` #### Explanation for Sample 2: There are some larger test cases. Make sure your answer is taken modulo $10^9+7$. Note that the answer for the second-to-last test case is $2^{45}\pmod{10^9+7}$. #### Test Point Properties: - For an additional $5\%$ of the testdata, $N \le 5$. - For an additional $10\%$ of the testdata, $M = N-1$. - For an additional $30\%$ of the testdata, if it is not true that for all $b$ we have $f_G(x,b)=f_G(y,b)$, then there exists $b$ such that $f_G(x,b)$ is true and $f_G(y,b)$ is false. - For an additional $45\%$ of the testdata, there are no additional constraints. Problem by: Benjamin Qi. Translated by ChatGPT 5