3755. SAU的大英雄
Great Heroes of SAU
time limit per test:1s
memory limit per test：256MB
Description:
As we all know, There are two ACM heros known as foreverlasting and fried-chicken in SAU. They are immersed in perfect love respectively. The following link tells the love story of fried-chicken.
likes graph and mathematics. He needs your help to solve an easy problem. You are given a simple undirected graph named "zjy" withnodes andedges. Please note that the graph is not necessarily connected. The nodes are labeled fromto .
wants to know how many "wbk" graphs in the "zjy" graph.
The above image defines a "wbk" graph.
Please note that two "wbk" graphs are considered different when there is at least one different edge between the two edge sets that make up the two "wbk" graphs.
In other word, the given graph is . You need to calculate the number of subgraphs which satisfy
Since the answer may be very large, wants to know the answer modulo .
Input Format:
The first line of input contains the integer , the number of test cases. The description of test cases follows.
The first line of each test case contains two integers, and —— the number of nodes and the number of edges, respectively.
Each of the next lines contains the description of an edge. Each line contains two integers and —— an edge connects node to node .
It is guaranteed that no two edges connect the same unordered pair of nodes.
Furthermore, it is guaranteed that the sum of over all test cases both do not exceed 3000.
Output Format:
For each testcase, output an integer representing the answer modulo .
Input Case
1 8 10 1 2 1 3 1 4 1 5 1 6 1 7 8 4 8 5 8 6 8 7
Output Case
1
SAU的大英雄
时间限制: 1s
内存限制：256MB
题目描述
众所周知，SAU 中有两位 ACM 英雄，他们分别是王芮糠和赵佳怡。他们分别沉浸在完美的爱情中。下面的链接讲述了赵佳怡的爱情故事。
喜欢图形和数学。他需要您的帮助来解决一个简单的问题。给你一个名为 "zjy" 的简单无向图，其中有个节点和条边。请注意，该图并不一定是连通的。节点的标记从到。
想知道 "zjy" 图中有多少个 "wbk "图。
上图定义了一个 "wbk" 图。
请注意，如果构成两个 "wbk" 图的两个边集之间至少有一条不同的边，那么这两个 "wbk" 图就被认为是不同的。
换句话说，给定的图是 。您需要计算满足 条件的子图 的个数。
由于答案可能很大， 希望知道答案的模数是 。
输入格式
第一行输入包含整数 ，即测试用例数。测试用例说明如下。
每个测试用例的第一行包含两个整数 和 ，分别是节点数和边数。
接下来的 行，每行包含一条边的描述。每行包含两个整数 和 —— 一条边连接节点 和节点 。
保证没有两条边连接相同的无序节点对。
此外，保证所有测试用例的 之和都不超过3000。
输出格式
针对每个测试用例，输出一个代表答案的整数，模数为 。
输入样例
1 8 10 1 2 1 3 1 4 1 5 1 6 1 7 8 4 8 5 8 6 8 7
输出样例
1
| 难度等级： | 0 |
| 总通过次数： | 1 |
| 总提交次数： | 16 |