2080: [USACO 2021 February Contest, Platinum] Problem 3. Counting Graphs

文件提交：无需freopen 内存限制：256 MB 时间限制：2.000 S
评测方式：普通裁判 命题人：
提交：1 解决：1

题目描述

Bessie has a connected, undirected graph $G$ with $N$ vertices labeled $1\ldots N$ and $M$ edges ($2\le N\le 10^2, N-1\le M\le \frac{N^2+N}{2}$). $G$ may contain self-loops (edges from nodes back to themselves), but no parallel edges (multiple edges connecting the same endpoints).

Let $f_G(a,b)$ be a boolean function that evaluates to true if there exists a path from vertex $1$ to vertex $a$ that traverses exactly $b$ edges for each $1\le a\le N$ and $0\le b$, and false otherwise. If an edge is traversed multiple times, it is included that many times in the count.

Elsie wants to copy Bessie. In particular, she wants to construct an undirected graph $G'$ such that $f_{G'}(a,b)=f_G(a,b)$ for all $a$ and $b$.

Your job is to count the number of distinct graphs $G'$ that Elsie may create, modulo $10^9+7$. As with $G$, $G'$ may contain self-loops but no parallel edges (meaning that there are $2^{\frac{N^2+N}{2}}$ distinct graphs on $N$ labeled vertices in total).

Each input contains $T$ ($1\le T\le \frac{10^5}{4}$) test cases that should be solved independently. It is guaranteed that the sum of $N^2$ over all test cases does not exceed $10^5$.  

输入

The first line of the input contains $T$, the number of test cases.

The first line of each test case contains the integers $N$ and $M$.

The next $M$ lines of each test case each contain two integers $x$ and $y$ ($1\le x\le y\le N$), denoting that there exists an edge between $x$ and $y$ in $G$.

Consecutive test cases are separated by newlines for readability.

输出

For each test case, the number of distinct $G'$ modulo $10^9+7$ on a new line.

样例输入 

1

5 4
1 2
2 3
1 4
3 5

样例输出 

3

提示

In the first test case, $G'$ could equal $G$ or one of the two following graphs:

5 4

1 2

1 4

3 4

3 5

or

5 5

1 2

2 3

1 4

3 4

3 5

SAMPLE INPUT:

7

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

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

5 7
1 2
1 3
1 5
2 4
3 3
3 4
4 5

6 6
1 2
2 3
3 4
4 5
5 6
6 6

6 7
1 2
2 3
1 3
1 4
4 5
5 6
1 6

10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

22 28
1 2
2 3
3 4
4 5
5 6
6 7
1 7
1 8
3 9
8 10
10 11
10 12
10 13
10 14
11 15
12 16
13 17
14 18
9 15
9 16
9 17
9 18
15 19
19 20
15 20
16 21
21 22
16 22

SAMPLE OUTPUT:

45
35
11
1
15
371842544
256838540

These are some larger test cases. Make sure to output the answer modulo $10^9+7$. Note that the answer for the second-to-last test case is $2^{45}\pmod{10^9+7}$.

SCORING:

  • All test cases in input 3 satisfy $N\le 5$.
  • All test cases in inputs 4-5 satisfy $M=N-1$.
  • For all test cases in inputs 6-11, if it is not the case that $f_G(x,b)=f_G(y,b)$ for all $b$, then there exists $b$ such that $f_G(x,b)$ is true and $f_G(y,b)$ is false.
  • Test cases in inputs 12-20 satisfy no additional constraints.

来源/分类

提交提交记录统计露一手!
codingfuture is powered by HUSTOJ, Theme by SYZOJ