HDU4997
Description
People are weak. Relationship between people like friendship or love is weak too. But a group of persons can have strong relationship, umm, 2edgeconnected relationship.
Suppose there are n persons. If two persons, A and B, are in a relationship, then we add an undirectional edge between them. In this way we can have a relationship graph, which is an undirectional graph without selfloops or multiple edges. If this graph is 2edgeconnected, then we say these persons have a strong relationship.
Now we have a group of persons without relationship between any two of them. And some pair of persons even hate each other. You will introduce some pairs of persons to know each other and set up a relationship between them to make the group of persons have a strong relationship. But notice that you can’t set up a relationship between a pair of persons who hate each other. How many ways you can do that? (Two ways are different if there exist a pair of persons which have relationship in one way but not in another way).
output the answer modulo 1e9+7
Input
The first line contains an integer $T$ , denoting the number of the test cases.
For each test case, the first line contains 2 integers n and m, denoting the number of persons in the group and the number of pairs of persons who hate each other. Then m lines follow, each line containing 2 integers $A$ and $B$, denoting that $A$ and B hate each other.
$T\leq5, 2\leq n\leq 10, 0\leq m\leq n*(n1)/2.$ The persons are indexed from $1$ .
Output
For each test case, output the answer in a line.
Sample Input
1
2
3
4
5
6 3
5 0
10 0
5 2
1 2
2 3Sample Output
1
2
3 253
466997276
18Hint
A 2edgeconnected graph is a graph which is connected and if you remove an edge from it, it is still connected.
Note that $n\geq 2$, so we can ignore the issue that whether a single vertex is 2edgeconnected or not :).
Solution
1.计算集合 $S$ 形成的连通图的方案数
直接做是 $3^n$ 这里说一下 $n^22^n$ 做法：定义集合幂级数的乘法为子集卷积，$f$ 为形成连通图的方案的集合幂级数，$g$ 为形成任意子图的方案的集合幂级数( $\varnothing$ 项的系数是 $0$ )
2. 计算集合 $S$ 形成的双连通图的方案数
为计算双连通子图的方案 $ans$，再记录一个h[S][T]
表示将 $S$ 划分为若干不相互连通的连通子集 $S_0,S_1\dots$ 使得所有子集 $S_0,S_1\dots$ 都有且仅有一条连向 $T$ 的边 （两条就双连通了）
一开始特别菜的不知道怎么预处理这个 $edge(S,T)$ 以为只能 $4^n$ 一看其他人写的直接 $E(S\oplus T)E(S)E(T)$即可，我容斥不过关
Code
1 
